Паралельне представлення алгоритмів. Лабораторна робота з Паралельні та розподілені обчислення . Робота № 522140

Паралельне представлення алгоритмів

Інформація про навчальний заклад

ВУЗ:

Національний університет Львівська політехніка

Інститут:

Не вказано

Факультет:

КН

Кафедра:

Кафедра ЕОМ

Інформація про роботу

Рік:

2013

Тип роботи:

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

Предмет:

Паралельні та розподілені обчислення

Завантажити

Частина тексту файла (без зображень, графіків і формул):

МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА” кафедра ЕОМ Лабораторна робота №2 з дисципліни “ Паралельні та розподілені обчислення “ на тему: “Паралельне представлення алгоритмів” Львів – 2011 Мета: Вивчити можливості паралельного представлення алгоритмів. Набути навиків такого представлення. Завдання: Запропонувати та реалізувати локально-рекурсивний алгоритм обчислення виразу: , де А та В матриці з елементами та , відповідно . Матриця А задається однозначно і залежить лише від розмірності даних. Для матриці В: заштрихована область — довільні цілі числа, відмінні від нуля, а незаштрихована область - нулі. № A B 18 1 2 3 … n-1 n 2 1 2 … n-2 n-1 3 2 1 … n-3 n-2 … n-1 n-2 n-3 … 1 2 n n-1 n-2 … 2 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 > 13) { MessageBox.Show("Матриця завелика для коректного відображення"); return; } arrayA = new int[N, N]; arrayB = new int[N, N]; for (int i = 0; i < N; i++) { for (int j = 0,res=i+1; j < i; j++,res--) { arrayA[i, j] = res; } for (int j = i,res=1; j < N; j++,res++) { arrayA[i, j] = res; } } int Temp = (N % 2 == 0) ? N / 2 : N / 2 + 1; Random rnd = new Random(DateTime.Now.Millisecond); for (int i = 0; i < N/2; i++) { for (int j = 0; j < N / 2; j++) { arrayB[i, j] = rnd.Next(9) + 1; } for (int j = N-1; j >= N-i-1; j--) { arrayB[i, j] = rnd.Next(9) + 1; } } for (int i = Temp; i < N; i++) { for (int j = 0; j < N-i; j++) { arrayB[i, j] = rnd.Next(9) + 1; } for (int j = Temp; j < N; j++) { arrayB[i, j] = rnd.Next(9) + 1; } } Show(arrayA, N, textBox1,true); Show(arrayB, N, textBox2,false); } } private void Show(int[,] arr,int N, TextBox txt, bool flag) { string probil = " "; string temp = ""; txt.Clear(); for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { if (i == j && flag) { txt.Text += arr[i, j].ToString(); switch (arr[i, j].ToString().Length) { case 1: temp = probil.Remove(0, probil.Length - 4); txt.Text += temp; break; case 2: temp = probil.Remove(0, probil.Length - 3); txt.Text += temp; break; case 3: temp = probil.Remove(0, probil.Length - 2); txt.Text += temp; break; case 4: temp = probil.Remove(0, probil.Length - 1); txt.Text += temp; break; } } else { txt.Text += arr[i, j].ToString() + probil; } } 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; } Count--; } } Show(arrC, N,"З одноразовим присвоєнням", Count); } private void localAlgorutm(int[,] arrA, int[,] arrB, int N) { int q = 0; int[,,] arrC = new int[N, N, N+1]; int Temp = (N % 2 == 0) ? N / 2 : N / 2 + 1; for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) { int t = (j < Temp) ? N - j : N; for (int k = (j < Temp) ? 0 : N - j-1; k < t; k++) { arrC[i, j, k + 1] = arrC[i, j, k] + arrA[i, k] * arrB[k, j]; arrC[i, j, N] = arrC[i, j, k + 1]; q += 2; } q--; } } 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 < N; i++) { for (int j = 0; j < N; 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 = 5; Висновок: на цій лабораторній роботі я вивчив можливості паралельного представлення алгоритмів. Виходячи з оптимізованого графу залежностей ми отримали високу ефективність обчислень.

Лабораторна робота Паралельні та розподілені обчислення

daniel

30.03.2013 22:18

Коментарі

Ви не можете залишити коментар. Для цього, будь ласка, або зареєструйтесь.

Ділись своїми роботами та отримуй миттєві бонуси!

поділитись