Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Паралельне представлення алгоритмів
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра ЕОМ
Інформація про роботу
Рік:
2013
Тип роботи:
Лабораторна робота
Предмет:
Паралельні та розподілені обчислення
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
кафедра ЕОМ
Лабораторна робота №2
з дисципліни “ Паралельні та розподілені обчислення “
на тему:
“Паралельне представлення алгоритмів”
Львів – 2011
Мета: Вивчити можливості паралельного представлення алгоритмів. Набути навиків такого представлення.
Завдання:
Запропонувати та реалізувати локально-рекурсивний алгоритм обчислення виразу: , де А та В матриці з елементами та , відповідно . Матриця А задається однозначно і залежить лише від розмірності даних. Для матриці В: заштрихована область — довільні цілі числа, відмінні від нуля, а незаштрихована область - нулі.
4
111…111
011…110
…
011…110
111…111
Послідовність виконання роботи:
Програма з одноразовим присвоюванням.
Програма об’єднана з програмою реалізації оптимізованого локально-рекурсивного алгоритма, і подана в пункті 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 Lab2
{
public partial class Form1 : Form
{
int[,] A;// = new int[10, 10];
int[,] B;// = new int[10, 10];
int Cnt = 0;
Random rnd = new Random();
public Form1()
{
InitializeComponent();
}
private void button1_Click(object sender, EventArgs e)
{
int n = Convert.ToInt32(textBox1.Text);
//fill Matrix A
A = new int[n, n];
B = new int[n, n];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
A[i, j] = 0;
}
}
for (int i = 0; i < n/2+1; i++)
{
for (int j = i; j < n-i; j++)
{
A[i, j] = 1;
A[n - 1 - i, j] = 1;
}
}
//output A
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
textBox2.Text += A[i, j].ToString() + " ";
}
textBox2.Text += Environment.NewLine;
}
textBox2.Text += Environment.NewLine;
//fill matrix B
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
B[i, j] = 0;
}
}
for (int i = n-1,k = 0; i > n/2-1; i--,k++)
{
for (int j = k; j < n; j++)
{
B[i, j] = rnd.Next(1,9);
}
}
//output B
for (int i = 0; i < n; i++)
{
for (int j = 0; j < n; j++)
{
textBox3.Text += B[i, j].ToString() + " ";
}
textBox3.Text += Environment.NewLine;
}
}
//function for output result
private void Show(int[, ,] C, int N, string msg, int cnt)
{
textBox4.Text += msg + Environment.NewLine;
for (int i = 0; i < C.GetLength(0); i++)
{
for (int j = 0; j < C.GetLength(1); j++)
{
textBox4.Text += C[i, j, N].ToString() + "\t";
}
textBox4.Text += Environment.NewLine;
}
textBox4.Text += "====================================" + Environment.NewLine;
textBox4.Text += "Кiлькiсть арифметичних операцій: " + cnt.ToString() + Environment.NewLine + Environment.NewLine;
}
void ArrayMul(int[,] A, int[,] B, int n)
{
int[, ,] C = 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++)
{
C[i, j, k + 1] = C[i, j, k] + A[i, k] * B[k, j];
Cnt += 2;
}
Cnt--;
}
}
Show(C, n, "З одноразовим присвоєнням", Cnt);
}
private void localAlgorutm(int[,] A, int[,] B, int n)
{
int cnt = 0;
int[, ,] C = new int[n, n, n + 1];
int temp = (n % 2 == 1) ? n / 2 -1 : n / 2-1;
for (int i = n-1,h=0; i > temp; i--)
{
h = 0;
for (int j = n-1-i; j < n; j++,h++)
{
for (int l = i,k=n-h; l >= n - j-1; k++, l--)
{
C[i, j, k] = C[i, j, k-1] + B[l,j];
cnt++;
}
cnt--;
}
}
for (int i = 0; i < n/2; i++)
{
for (int j = 0; j < n; j++)
{
C[i, j, n] = C[n - 1 - i, j, n];
}
}
Show(C, n, "Локально-рекурсивний алгоритм", cnt);
}
private void button2_Click(object sender, EventArgs e)
{
int n = Convert.ToInt32(textBox1.Text);
ArrayMul(A, B, n);
}
private void button3_Click(object sender, EventArgs e)
{
int n = Convert.ToInt32(textBox1.Text);
localAlgorutm(A, B, n);
}
private void button4_Click(object sender, EventArgs e)
{
textBox1.Clear();
textBox2.Clear();
textBox3.Clear();
textBox4.Clear();
}
}
}
Текст програми, що реалізовує оптимізований локально-рекурсивний алгоритм:
Результат виконання програми для n = 4;
Висновок: на цій лабораторній роботі я вивчив можливості паралельного представлення алгоритмів. Виходячи з оптимізованого графу залежностей ми отримали високу ефективність обчислень.
28.03.2013 13:05
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора