Приклад паралельного алгоритму для обчислення площi прямокутника

Представлена тут програма iлюструє простий, але цiкавий приклад використання обчислювальної моделi алгоритму у виглядi графа "операцiї-операнди" для побудови конвейера команд.

Розглянемо задачу обчислення площi прямокутника, заданого координатами своїх кутiв:

Площу такого прямокутника можна обрахувати за такою формулою:

s = (x2 - x1) * (y2 - y1)

Розпаралелимо її:

s = (x2 - x1) * (y2 - y1) = (x2 * y2 - x2 * y1) + (x1 * y1 - x1 * y2)

Побудуємо граф "операцiї-операнди"

У верхньому рядочку малюнка розташованi операнди, значення яких подаються на вхiд потокiв, що виконують опеерацiю множення.

Результати цих операцiй передаються потокам, якi виконують операцiю вiднiмання.

На третьому етапi роботи конвейера результати вiднiмання збирає останнiй процес i виконує операцiю їх складання.

Для реалiзацiї такого алгоритму створимо клас Calculator, який буде виконувати елементарнi математичнi дiї.

Для того, щоб цей клас можна було запускати як окремий потiк, вiн повинен iмплементувати iнтерфейс Runnable.

Математичнi операцiї, якi необхiдно виконати визначаються константами opSum, opSub, opMult та opDiv.

У об'єкт класу Calculator код операц?ї передається за допомогою параметру cop.

Початковi данi, промiжнi та кiнцевi результати зберiгаються у лiнiйному масивi data[] класу RectangleSquareCalc.

Цей масив є розподiленим ресурсом.

Класу Calculator пiд час створення передаються лише iндекси вiдповiдних комiрок у цому масивi.

А саме:

• op1 - iндекс першого операнду;
• op2 - iндекс другого операнду;
• res - iндекс результату виконання операцiї.

Крым того, кожному примiрнику класа Calculator передається його власне iм'я name та посилання на батькiвський об'єкт-менеджер RectangleSquareCalc.

У процесi роботи кожен примiрник класу Calculator аналiзує наданий йому код операцiї, бере операнди iз загального масиву, виконує над ними вказану операцiю та кладе результат у загальний масив за його iндексом.

import java.util.concurrent.*; class Calculator implements Runnable { public final static int opSum = 1; public final static int opSub = 2; public final static int opMult = 3; public final static int opDiv = 4; int codeOp; int operator1; int operator2; int result; String threadName; RectangleSquareCalc manager; Calculator( String name, int cop, int op1, int op2, int res, RectangleSquareCalc rsc) { threadName = name; codeOp = cop; operator1 = op1; operator2 = op2; result = res; manager = rsc; System.out.println( threadName + " - Created"); } public void run() { System.out.println( threadName + " - Start of Work"); while (!manager.stopFlag) { if (manager.flags[operator1] && manager.flags[operator2]) { switch(codeOp) { case opSum: manager.data[result] = manager.data[operator1] + manager.data[operator2]; System.out.println( threadName + ": Sum: " + operator1 + " + " + operator2 + " ==> " + result); break; case opSub: manager.data[result] = manager.data[operator1] - manager.data[operator2]; System.out.println( threadName + ": Sub: " + operator1 + " + " + operator2 + " ==> " + result); break; case opMult: manager.data[result] = manager.data[operator1] * manager.data[operator2]; System.out.println( threadName + ": Mult: " + operator1 + " + " + operator2 + " ==> " + result); break; case opDiv: manager.data[result] = manager.data[operator1] / manager.data[operator2]; System.out.println( threadName + ": Div: " + operator1 + " + " + operator2 + " ==> " + result); break; default: break; } manager.flags[operator1] = false; manager.flags[operator2] = false; manager.flags[result] = true; } Thread.yield(); } } }

Налагодження конвейеру згiдно з наведеним вище графом "операцiї-операнди" виконаємо за допомогою класу RectangleSquareCalc.

public class RectangleSquareCalc { double data[]; boolean flags[]; boolean stopFlag = false; RectangleSquareCalc( double x1, double y1, double x2, double y2) { data = new double[15]; flags = new boolean[15]; int pos = 0; flags[pos] = true; data[pos++] = x2; flags[pos] = true; data[pos++] = y2; flags[pos] = false; data[pos++] = 0.0; flags[pos] = true; data[pos++] = x2; flags[pos] = true; data[pos++] = y1; flags[pos] = false; data[pos++] = 0.0; flags[pos] = true; data[pos++] = x1; flags[pos] = true; data[pos++] = y2; flags[pos] = false; data[pos++] = 0.0; flags[pos] = true; data[pos++] = x1; flags[pos] = true; data[pos++] = y1; flags[pos] = false; data[pos++] = 0.0; } public static void main( String argc[]) { System.out.println( "Main process started"); RectangleSquareCalc rsc = new RectangleSquareCalc( 1.0, 2.0, 3.0, 4.0); ExecutorService execSvc = Executors.newFixedThreadPool( 7); execSvc.execute( new Calculator( "Mult_1", Calculator.opMult, 0, 1, 2, rsc)); execSvc.execute( new Calculator( "Mult_2", Calculator.opMult, 3, 4, 5, rsc)); execSvc.execute( new Calculator( "Mult_3", Calculator.opMult, 6, 7, 8, rsc)); execSvc.execute( new Calculator( "Mult_4", Calculator.opMult, 9, 10, 11, rsc)); execSvc.execute( new Calculator( "Sub_5", Calculator.opSub, 2, 5, 12, rsc)); execSvc.execute( new Calculator( "Sub_6", Calculator.opSub, 11, 8, 13, rsc)); execSvc.execute( new Calculator( "Sum_7", Calculator.opSum, 12, 13, 14, rsc)); while (!rsc.flags[14]) { try { Thread.sleep( 2); } catch(InterruptedException e) {} } rsc.stopFlag = true; System.out.println(); for (int i = 0; i < 4; ++i) { for (int j = 0; j < 3; ++j) { System.out.print( "( " + (3 * i + j) + " ): " + rsc.data[3 * i + j] + ", "); } System.out.println(); } System.out.println( "( " + 12 + " ): " + rsc.data[12] + ", "); System.out.println( "( " + 13 + " ): " + rsc.data[13] + ", "); System.out.println( "( " + 14 + " ): " + rsc.data[14] + ", "); execSvc.shutdown(); System.out.println( "Main process ended"); } }

Завдання:

1. Розглянути, вiдкомпiлювати та запустити на виконання наведенi приклади.
2. З'ясувати принципи взємодiї та синхронiзацiї потокiв при використаннi конвейеру команд.
3. З'ясувати особливостi програмування та застосування конвейеру команд.