МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” кафедра ЕОМ
Лабораторна робота №2 з дисципліни “ Паралельні та розподілені обчислення “ на тему: “Паралельне представлення алгоритмів” Львів – 2011 Мета: Вивчити можливості паралельного представлення алгоритмів. Набути навиків такого представлення. Завдання: Запропонувати та реалізувати локально-рекурсивний алгоритм обчислення виразу:
, де А та В матриці з елементами
та
, відповідно
. Матриця А задається однозначно і залежить лише від розмірності даних. Для матриці В: заштрихована область — довільні цілі числа, відмінні від нуля, а незаштрихована область - нулі. № A B 1 n 0 .... 0 0 n-1...0 .... 0 .... 1    Послідовність виконання роботи: Програма з одноразовим присвоюванням. Програма об’єднана з програмою реалізації оптимізованого локально-рекурсивного алгоритма, і подана в пункті 6. Рекурсивні рівняння: Cij(k+1)=Cij(k)+Aij(k)*Bij(k), де Aij(k)=A[i][j], Bij(k)=B[i][j], k - індекс рекурсії. Граф залежностей(n=4):
Оптимізований граф залежностей(n=4):
Аналітичні оцінки кількості арифметичних операцій та їх порівняння. В локалізованому графі залежностей кількість операцій рівна N2(2N-1) де n кількість стовпців чи рядків матриці.(Для обчислення кожного з N2 елементів необхідно 2N-1 операцій). Текст програми, що реалізовує оптимізований локально-рекурсивний алгоритм: using System; using System.Collections.Generic; using System.ComponentModel; using System.Data; using System.Drawing; using System.Linq; using System.Text; using System.Windows.Forms; namespace Pro_lab2 { public partial class Form1 : Form { public Form1() { InitializeComponent(); } int N=0; int[,] arrayA; int[,] arrayB; private void maskedTextBox1_KeyPress(object sender, KeyPressEventArgs e) { if (e.KeyChar == Convert.ToChar(13)) { N = Int32.Parse(maskedTextBox1.Text); if (N > 16) { MessageBox.Show("Матриця завелика для коректного відображення"); return; } arrayA = new int[N, N]; arrayB = new int[N, N]; for (int i = 0; i < N; i++) { arrayA[i, i] = N - i; } Random rnd = new Random(DateTime.Now.Millisecond); for (int i = 0; i < N; i++) { for (int j = i; j < N; j++) { arrayB[i, j] = rnd.Next(9)+1; } } Show(arrayA, N, textBox1); Show(arrayB, N, textBox2); } } private void Show(int[,] arr,int N, TextBox txt) { txt.Clear(); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { txt.Text += arr[i, j].ToString() + " "; } txt.Text += Environment.NewLine; } } private void button1_Click(object sender, EventArgs e) { Count = 0; textBox3.Clear(); if (N != Int32.Parse(maskedTextBox1.Text)) { KeyPressEventArgs e1 = new KeyPressEventArgs(Convert.ToChar(13)); maskedTextBox1_KeyPress(sender, e1); } ArrayMul(arrayA, arrayB, N); localAlgorutm(arrayA, arrayB, N); } int Count = 0; void ArrayMul(int[,] arrA, int[,] arrB, int N) { int[,,] arrC = new int[N, N, N+1]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { for (int k = 0; k < N; k++) { arrC[i, j, k+1] = arrC[i, j, k] + arrA[i, k] * arrB[k, j]; Count += 2; } } } Show(arrC, N,"З одноразовим присвоєнням", Count); } private void localAlgorutm(int[,] arrA, int[,] arrB, int N) { int q = 0; int[, ,] TempA = new int[N, N, N + 1]; int[, ,] TempB = new int[N, N, N + 1]; int[, ,] arrC = new int[N, N, N + 1]; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { TempA[i, j, 0] = arrA[i, j]; TempB[i, j, 0] = arrB[i, j]; } } for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) { TempA[i, k, j + 1] = TempA[i, k, j]; TempB[k, j, i + 1] = TempB[k, j, i]; if (TempA[i, k, 0] == 1 && TempB[k, j, 0] == 1) { arrC[i, j, k + 1] = arrC[i, j, k]+1; q++; continue; } if (TempA[i, k, 0] != 0 && TempB[k, j, 0] != 0) { arrC[i, j, k + 1] = arrC[i, j, k] + TempA[i, k, j] * TempB[k, j, i]; q+=2; } else arrC[i, j, k + 1] = arrC[i, j, k]; } Show(arrC, N,"Локально-рекурсивний алгоритм" ,q); } private void Show(int[, ,] arrC, int N, string Mess, int q) { textBox3.Text += Mess + Environment.NewLine; for (int i = 0; i < arrC.GetLength(0); i++) { for (int j = 0; j < arrC.GetLength(1); j++) { textBox3.Text += arrC[i, j, N].ToString() + "\t"; } textBox3.Text += Environment.NewLine; } textBox3.Text += "----------------------------------------------------" + Environment.NewLine; textBox3.Text += "Кiлькiсть арифметичних операцій: " + q.ToString() + Environment.NewLine; } } } Результат виконання програми для n = 4;
Висновок: виконуючи лабораторну роботу, я отримала навики паралельного обчислення алгоритмів на базі множення матриць, також навчилась реалізовувати алгоритм з одноразовим присвоєнням і локально-рекурсивний алгоритм, який працює на базі локалізованого графа.