Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Паралельне представлення алгоритмів
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2013
Тип роботи:
Лабораторна робота
Предмет:
Паралельні та розподілені обчислення
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
кафедра ЕОМ
Лабораторна робота №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;
Висновок: виконуючи лабораторну роботу, я отримала навики паралельного обчислення алгоритмів на базі множення матриць, також навчилась реалізовувати алгоритм з одноразовим присвоєнням і локально-рекурсивний алгоритм, який працює на базі локалізованого графа.
29.03.2013 10:07
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора