Организация конвейерных вычислений

Размещено на http://allbest.ru

Министерство образования и науки Украины

Севастопольский национальный технический университет

Кафедра Кибернетики и вычислительной техники

Лабораторная работа

по курсу: «Параллельные и распределенные вычисления»

Организация конвейерных вычислений

Выполнил: ст. гр. М-34д

Ярославцев Д.А.

Проверил: Абрамов Т.А.

Севастополь

2010 г.



1. Исходные данные

программный конвейерный семафор синхронизация

Цель:

Исследовать методы и средства организации конвейерной обработки данных.

Задание на лабораторную работу:

Разработать в соответствии с вариантом задания программу, выполняющую конвейерную (поэтапную) обработку массива данных

Исследовать поведение программы при использовании различных методов синхронизации (семафоры, событийные переменные)

Проанализировать полученные результаты.

2. Ход работы

Конвейерная обработка данных применяется при решении сложных вычислительных задач, допускающих разбиение процесса решения на относительно независимые части. В этом случае выходные данные (результаты работы) очередного процесса являются входными данными следующего процесса и т.д. Соответственно, за счет параллельной обработки сокращается общее время решения задачи. Типовая схема конвейерной обработки выглядит следующим образом:



В нашем случае существует всего 4 процесса, один из которых является генератором. Генератор формирует массив из 1000 случайных элементов.

После этого первый процесс берёт этот массив из буфера генератора и производит над ним следующие действия:

- формируется массив из 100 чисел;

- каждому числу массива присваивается минимальное число из 10 по порядку чисел первоначального массива;

- сформированный новый массив помещается в буфер 1 процесса.

После этого второй процесс берёт из буфера первого процесса исходный массив из 100 чисел и производит следующие действия:

- формируется массив из 10 чисел;

- каждому числу массива присваивается минимальное число из 10 по порядку чисел первоначального массива;

- сформированный новый массив помещается в буфер 2 процесса.

После этого третий процесс берёт из буфера второго процесса исходный массив из 10 чисел и производит следующие действия:

- вывод на экран этих чисел.

Регулировку данных конвейерных вычислений будем производить при помощи уже известных нам семафоров. Для этого создадим пары семафоров. Открытый семафор с четным номером сигнализирует о том, что соответствующий буфер свободен для записи информации, открытый семафор с нечетным номером - соответствующий буфер заполнен и доступен для выборки. В таком случае текст программы будет следующим.



3. Текст программы

import java.util.concurrent.*;

import java.util.Random;

class SEMAPHORE {

public static void main(String args[])

{Q q = new Q();

new Generator(q,0);

new Worker(q,1);

new Worker(q,2);

new Worker(q,3);

try {Thread.sleep(5000);} catch(InterruptedException e) {} ;

q.work = false;

System.out.println("Количество полных циклов:"+q.count);}}

class Q

{int n;

boolean work = true;

Semaphore s02 = new Semaphore(1,true);

Semaphore s11 = new Semaphore(0,true); Semaphore s12 = new Semaphore(1,true);

Semaphore s21 = new Semaphore(0,true); Semaphore s22 = new Semaphore(1,true);

Semaphore s31 = new Semaphore(0,true);

int [] A = new int[1000];

int [] B = new int[100];

int [] C = new int[10];

int count=0;}

class Generator implements Runnable

{Q q;

int num;

Generator(Q q,int num)

{this.q = q;

this.num = num;

new Thread(this, "Generator "+num).start();}

public int number(int begin, int end) {return (int)(begin + Math.random()*(end-begin+1));}

public void run() {

Thread t = Thread.currentThread();

while (q.work)

{try { q.s02.acquire(); } catch(InterruptedException e) {} ;

System.out.println(t.getName()+" start");

for(int i=0; i<1000; i++){

q.A[i] =number(10,1000);}

try { Thread.sleep(100); } catch(InterruptedException e) {} ;

System.out.println(t.getName()+" stop");

q.s11.release();}}

class Worker implements Runnable

{Q q;

int num;

Worker(Q q,int num)

{this.q = q;

this.num = num;

new Thread(this, "Worker "+num).start();}

public void run()

{Thread t = Thread.currentThread();

while (q.work)

{switch (num)

{case 1: try { q.s11.acquire(); } catch(InterruptedException e) {} ;

try { q.s12.acquire(); } catch(InterruptedException e) {} ; break;

case 2: try { q.s21.acquire(); } catch(InterruptedException e) {} ;

try { q.s22.acquire(); } catch(InterruptedException e) {} ; break;

case 3: try { q.s31.acquire(); } catch(InterruptedException e) {} ;}

System.out.println(t.getName()+" start");

int min=Integer.MAX_VALUE;

switch (num) {

case 1:

int k=0;

for (int i=0; i<100; i++) {

min=q.A[k];

for (int j=k; j<k+10; j++) { if ( (j+1) == 1000 ) break;

if ( min > q.A[j+1] )

min = q.A[j+1]; }

q.B[i]=min;

k+=10; }

break;

case 2:

k=0;

for (int i=0; i<10; i++){

min=q.B[k];

for (int j=k; j<k+10; j++) {

if ( (j+1) == 100 ) break;

if ( min > q.B[j+1] )

min = q.B[j+1]; }

q.C[i]=min;

k+=10;}

break;

case 3:

for (int i=0; i<10; i++)System.out.print(q.C[i] + " ");

System.out.println();

q.count++;

break;}

try { Thread.sleep(100); } catch(InterruptedException e) {} ;

System.out.println(t.getName()+" stop");

switch (num)

{case 1: q.s21.release(); q.s02.release(); break;

case 2: q.s31.release(); q.s12.release(); break;

case 3: q.s22.release(); break;}}

4. Результаты

Generator 0 start

Generator 0 stop

Worker 1 start

Worker 1 stop

Worker 2 start

Generator 0 start

Worker 2 stop

Worker 3 start

20 21 11 14 10 18 28 36 11 20

Generator 0 stop

Worker 1 start

Worker 3 stop

Worker 1 stop

Worker 2 start

Generator 0 start

Worker 2 stop

Worker 3 start

17 16 19 27 14 14 10 12 15 10

Generator 0 stop

Worker 1 start

Worker 3 stop

Worker 1 stop

Worker 2 start

Generator 0 start

Generator 0 stop

Worker 2 stop

Worker 3 start

11 17 12 11 10 32 31 43 13 13

Worker 1 start

Worker 3 stop

Worker 1 stop

Generator 0 start

Worker 2 start

Worker 2 stop

Worker 3 start

17 14 39 19 10 19 16 16 20 33

Generator 0 stop

Worker 1 start

Worker 3 stop

Worker 1 stop

Worker 2 start

Generator 0 start

Generator 0 stop

Worker 2 stop

Worker 3 start

13 11 32 22 15 23 22 12 12 10

Worker 1 start

Worker 3 stop

Worker 1 stop

Worker 2 start

Generator 0 start

Worker 2 stop

Generator 0 stop

Worker 3 start

34 11 10 31 30 15 10 13 30 12

Worker 1 start

Worker 1 stop

Worker 3 stop

Worker 2 start

Generator 0 start

Worker 2 stop

Generator 0 stop

Worker 1 start

Worker 3 start

15 18 18 10 14 14 18 22 20 15

Worker 1 stop

Generator 0 start

Worker 3 stop

Worker 2 start

Generator 0 stop

Worker 2 stop

Worker 3 start

11 13 13 38 10 16 10 10 18 13

Worker 1 start

Worker 1 stop

Generator 0 start

Worker 3 stop

Worker 2 start

Worker 2 stop

Generator 0 stop

Worker 1 start

Worker 3 start

14 18 11 23 46 20 18 17 20 24

Worker 1 stop

Worker 3 stop

Generator 0 start

Worker 2 start

Worker 2 stop

Generator 0 stop

Worker 3 start

11 13 16 10 11 22 26 10 12 41

Worker 1 start

Worker 3 stop

Worker 1 stop

Generator 0 start

Worker 2 start

Worker 2 stop

Generator 0 stop

Worker 1 start

Worker 3 start

27 52 10 40 12 23 20 11 19 53

Worker 1 stop

Generator 0 start

Worker 3 stop

Worker 2 start

Generator 0 stop

Worker 2 stop

Worker 3 start

10 22 22 12 16 22 33 18 18 11

Worker 1 start

Worker 1 stop

Generator 0 start

Worker 3 stop

Worker 2 start

Generator 0 stop

Worker 2 stop

Worker 3 start

16 28 10 17 41 27 16 33 19 14

Worker 1 start

Worker 3 stop

Worker 1 stop

Worker 2 start

Generator 0 start

Worker 2 stop

Worker 3 start

Generator 0 stop

16 10 19 11 12 26 10 10 19 13

Worker 1 start

Worker 3 stop

Worker 1 stop

Generator 0 start

Worker 2 start

Generator 0 stop

Worker 2 stop

Worker 3 start

11 23 19 12 10 16 16 13 22 20

Worker 1 start

Worker 3 stop

Worker 1 stop

Worker 2 start

Generator 0 start

Generator 0 stop

Worker 2 stop

Worker 3 start

15 15 11 19 22 10 14 10 16 12

Worker 1 start

Worker 3 stop

Worker 1 stop

Worker 2 start

Generator 0 start

Generator 0 stop

Worker 2 stop

Worker 3 start

10 13 25 17 10 12 19 15 10 15

Worker 1 start

Worker 3 stop

Worker 1 stop

Worker 2 start

Generator 0 start

Generator 0 stop

Worker 2 stop

Worker 3 start

12 10 23 12 14 22 11 20 20 14

Worker 1 start

Worker 3 stop

Worker 1 stop

Worker 2 start

Generator 0 start

Worker 2 stop

Worker 3 start

12 11 20 13 41 12 14 12 12 24

Generator 0 stop

Worker 1 start

Worker 3 stop

Worker 1 stop

Worker 2 start

Generator 0 start

Worker 2 stop

Worker 3 start

22 14 37 10 10 10 10 10 28 14

Generator 0 stop

Worker 1 start

Worker 1 stop

Worker 3 stop

Worker 2 start

Generator 0 start

Generator 0 stop

Worker 2 stop

Worker 3 start

17 10 18 10 14 17 21 28 18 31

Worker 1 start

Worker 3 stop

Worker 1 stop

Worker 2 start

Generator 0 start

Generator 0 stop

Worker 2 stop

Worker 3 start

10 11 11 13 13 12 12 21 15 22

Worker 1 start

Worker 1 stop

Generator 0 start

Worker 3 stop

Worker 2 start

Generator 0 stop

Worker 2 stop

Worker 3 start

10 60 15 15 12 24 11 17 27 28

Worker 1 start

Worker 1 stop

Generator 0 start

Worker 3 stop

Worker 2 start

Generator 0 stop

Worker 2 stop

Worker 3 start

15 16 20 19 23 17 26 16 16 53

Worker 1 start

Количество полных циклов:24

Worker 3 stop

Worker 1 stop

Generator 0 start

Worker 2 start

Worker 2 stop

Generator 0 stop

Как можно видеть, все числа в последнем массиве являются минимальными. Также тот факт, что Генератор начинает работать после окончания работы первого процесса (так как первому процессу нужен заполненный буфер генератора и собственный чистый буфер), позволяет выиграть в скорости и разумном использовании выделенного времени.

Выполним синхронизацию потоков с помощью событийных переменных. Код модифицированной программы приведен ниже.

import java.util.concurrent.locks.*;

public class SOBITIINIE1 {

static int begin1=0;

static int end1=0;

public static void main(String[]args) {

begin1=10;

end1=1000;

Q q = new Q();

new Process(q,0);

new Process(q,1);

new Process(q,2);

new Process(q,3);

try {Thread.sleep(50);} catch(InterruptedException e) {};

try{q.lock.lock();

q.G.signal(); // запускаем генератор

// try {Thread.sleep(100);} catch(InterruptedException e) {};

q.W1.signal();

q.W2.signal();

// q.W3.signal();

} finally { q.lock.unlock(); }

try {Thread.sleep(5000);} catch(InterruptedException e) {};

q.work = false;}}

class Q {

int A [] = new int[1000];

int B [] = new int[100];

int C [] = new int[10];

boolean work = true;

final ReentrantLock lock = new ReentrantLock();

final Condition G = lock.newCondition();

final Condition W1 = lock.newCondition();

final Condition W2 = lock.newCondition();

final Condition W3 = lock.newCondition();}

class Process implements Runnable{

Q q;

int num;

boolean first=true;

Process(Q q,int num) {

this.q = q;

this.num = num;

if(num==0)new Thread(this, "Generator "+num).start();

else new Thread(this, "Worker "+num).start(); }

public int number(int begin, int end) {return (int)(begin + Math.random()*(end-begin+1));}

public void run() {

Thread t = Thread.currentThread();

while (q.work) {

switch (num) {

case 0: { // Генератор ожидает сигнала

q.lock.lock(); try{

try {q.G.await(); } catch(InterruptedException e) {}

} finally { q.lock.unlock();}

break; }

case 1: { // Worker 1 ожидает сигнала

q.lock.lock(); try{

try {q.W1.await(); q.W1.await();} catch(InterruptedException e) {}

} finally { q.lock.unlock(); }

break; }

case 2: { // Worker 2 ожидает сигнала

q.lock.lock(); try{

try {q.W2.await(); q.W2.await();} catch(InterruptedException e) {}

} finally { q.lock.unlock(); }

break; }

case 3: { // Worker 3 ожидает сигнала

q.lock.lock(); try{

try {q.W3.await(); } catch(InterruptedException e) {}

} finally { q.lock.unlock(); }

break; }}

switch (num) {

case 0: { // Генератор работает

System.out.println(t.getName()+" start");

try { Thread.sleep(number(0,150)); } catch(InterruptedException e) {} ;

for (int i=0; i<1000; i++) {q.A[i]=number(SOBITIINIE1.begin1, SOBITIINIE1.end1); }

System.out.println(t.getName()+" stop");

break;}

case 1: { // Worker 1 работает

System.out.println(t.getName()+" start");

try { Thread.sleep(number(0,150)); } catch(InterruptedException e) {} ;

int k=0; for (int i=0; i<100; i++) { int min=q.A[k];

for (int j=k; j<k+10; j++) { if ((j+1)==1000) break;

if ( min > q.A[j+1] ) min = q.A[j+1]; } q.B[i]=min; k+=10; }

System.out.println(t.getName()+" stop");

break;}

case 2: { // Worker 2 работает

System.out.println(t.getName()+" start");

try { Thread.sleep(number(0,150)); } catch(InterruptedException e) {} ;

int k=0; for (int i=0; i<10; i++){

int min=q.B[k]; for (int j=k; j<k+10; j++) {

if ( (j+1) == 100 ) break;

if ( min > q.B[j+1] )min=q.B[j+1]; }

q.C[i]=min; k+=10;}

System.out.println(t.getName()+" stop");

break;}

case 3: { // Worker 3 работает

System.out.println(t.getName()+" start");

try { Thread.sleep(number(0,150)); } catch(InterruptedException e) {} ;

for (int i=0; i<10; i++)System.out.print(q.C[i] + " ");

System.out.println();

System.out.println(t.getName()+" stop");

break;}}

switch (num) {

case 0: { // Генератор будит следующий поток

q.lock.lock(); try{

q.W1.signal();

} finally { q.lock.unlock();}

break; }

case 1: { // Worker 1 будит следующие потоки

q.lock.lock(); try{

q.W2.signal();

q.G.signal();

} finally { q.lock.unlock(); }

break; }

case 2: { // Worker 2 будит следующие потоки

q.lock.lock(); try{

q.W1.signal();

q.W3.signal();

} finally { q.lock.unlock(); }

break; }

case 3: { // Worker 3 будит следующий поток

q.lock.lock (); try{

q.W2.signal();

} finally { q.lock.unlock(); }

break; }}

Получаем следующие результаты:

Generator 0 start

Generator 0 stop

Worker 1 start

Worker 1 stop

Worker 2 start

Generator 0 start

Generator 0 stop

Worker 2 stop

Worker 1 start

Worker 3 start

15 20 33 11 17 14 10 18 26 24

Worker 3 stop

Worker 1 stop

Worker 2 start

Generator 0 start

Generator 0 stop

Worker 2 stop

Worker 1 start

Worker 3 start

Worker 1 stop

Generator 0 start

Generator 0 stop

14 20 21 21 12 14 15 28 12 11

Worker 3 stop

Worker 2 start

Worker 2 stop

Worker 1 start

Worker 3 start

Worker 1 stop

Generator 0 start

Generator 0 stop

16 16 11 46 24 11 14 25 10 30

Worker 3 stop

Worker 2 start

Worker 2 stop

Worker 1 start

Worker 3 start

23 39 11 11 15 63 51 12 16 13

Worker 3 stop

Worker 1 stop

Worker 2 start

Generator 0 start

Worker 2 stop

Worker 3 start

11 18 35 11 12 41 31 17 18 16

Worker 3 stop

Generator 0 stop

Worker 1 start

Worker 1 stop

Worker 2 start

Generator 0 start

Generator 0 stop

Worker 2 stop

Worker 1 start

Worker 3 start

Worker 1 stop

Generator 0 start

14 15 13 10 15 13 12 12 21 25

Worker 3 stop

Worker 2 start

Generator 0 stop

Worker 2 stop

Worker 1 start

Worker 3 start

Worker 1 stop

Generator 0 start

Generator 0 stop

13 31 16 15 16 21 19 17 10 32

Worker 3 stop

Worker 2 start

Worker 2 stop

Worker 1 start

Worker 3 start

16 16 13 25 38 26 23 13 12 21

Worker 3 stop

Worker 1 stop

Worker 2 start

Generator 0 start

Generator 0 stop

Worker 2 stop

Worker 1 start

Worker 3 start

21 12 13 21 19 27 31 17 26 15

Worker 3 stop

Worker 1 stop

Worker 2 start

Generator 0 start

Worker 2 stop

Worker 3 start

27 22 12 19 12 17 22 11 14 24

Worker 3 stop

Generator 0 stop

Worker 1 start

Worker 1 stop

Worker 2 start

Generator 0 start

Generator 0 stop

Worker 2 stop

Worker 1 start

Worker 3 start

25 11 15 14 19 15 28 11 36 16

Worker 3 stop

Worker 1 stop

Worker 2 start

Generator 0 start

Generator 0 stop

Worker 2 stop

Worker 1 start

Worker 3 start

Worker 1 stop

Generator 0 start

10 13 20 12 22 28 11 10 18 39

Worker 3 stop

Worker 2 start

Worker 2 stop

Worker 3 start

Generator 0 stop

Worker 1 start

Worker 1 stop

Generator 0 start

Generator 0 stop

13 13 39 19 15 14 12 10 31 28

Worker 3 stop

Worker 2 start

Worker 2 stop

Worker 1 start

Worker 3 start

Worker 1 stop

Generator 0 start

Generator 0 stop

16 15 14 11 16 32 19 16 24 16

Worker 3 stop

Worker 2 start

Worker 2 stop

Worker 1 start

Worker 3 start

13 26 15 15 19 13 11 17 17 46

Worker 3 stop

Worker 1 stop

Worker 2 start

Generator 0 start

Worker 2 stop

Worker 3 start

11 12 13 30 14 16 10 23 10 18

Worker 3 stop

Generator 0 stop

Worker 1 start

Worker 1 stop

Worker 2 start

Generator 0 start

Worker 2 stop

Worker 3 start

Generator 0 stop

Worker 1 start

Worker 1 stop

Generator 0 start

21 32 18 18 18 22 10 19 12 13

Worker 3 stop

Worker 2 start

Generator 0 stop

Worker 2 stop

Worker 1 start

Worker 3 start

53 10 16 16 29 13 21 15 17 13

Worker 3 stop

Worker 1 stop

Worker 2 start

Generator 0 start

Worker 2 stop

Worker 3 start

Generator 0 stop

Worker 1 start

Worker 1 stop

Generator 0 start

25 11 10 12 13 15 19 10 16 11

Worker 3 stop

Worker 2 start

Generator 0 stop

Worker 2 stop

Worker 1 start

Worker 3 start

Worker 1 stop

Generator 0 start

16 14 12 18 32 16 12 22 38 16

Worker 3 stop

Worker 2 start

Generator 0 stop

Worker 2 stop

Worker 1 start

Worker 3 start

14 24 13 15 11 11 17 12 12 36

Worker 3 stop

Worker 1 stop

Worker 2 start

Generator 0 start

Worker 2 stop

Worker 3 start

Generator 0 stop

Worker 1 start

18 36 10 17 20 10 26 31 22 12

Worker 3 stop

Worker 1 stop

Worker 2 start

Generator 0 start

Generator 0 stop

Worker 2 stop

Worker 1 start

Worker 3 start

Worker 1 stop

Generator 0 start

Generator 0 stop

17 12 11 11 26 15 27 27 40 22

Worker 3 stop

Worker 2 start

Worker 2 stop

Worker 1 start

Worker 3 start

12 26 19 16 14 11 16 18 19 29

Worker 3 stop

Worker 1 stop

Worker 2 start

Generator 0 start

Generator 0 stop

Worker 2 stop

Worker 3 start

Worker 3 stop

Как можно видеть, все числа в последнем массиве являются минимальными. Генератор начинает работать после окончания работы первого процесса (так как первому процессу нужен заполненный буфер генератора и собственный чистый буфер), что позволяет выиграть в скорости работы. Задача решена.



Выводы

Выполнив работу, я исследовал способы обработки конвейерных процессов. В результате чего была создана программная модель для регулировки 3 процессов и одного генератора, выполняющие вычисления в соответствии с вариантом.

Размещено на Allbest.ru

...