Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
ВИКОРИСТАННЯ ФУНКЦІОНАЛЬНОЇ ДЕКОМПОЗИЦІЇ ДЛЯ РОЗВ’ЯЗКУ ОБЧИСЛЮВАЛЬНИХ ЗАДАЧ
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
ІКТА
Факультет:
Комп'ютерна інженерія
Кафедра:
ЕОМ
Інформація про роботу
Рік:
2015
Тип роботи:
Лабораторна робота
Предмет:
Паралельні та розподілені обчислення
Група:
КІ 41
Частина тексту файла (без зображень, графіків і формул):
Мiнiстерство освiти і науки, молоді та спорту України
Національний університет “Львівська політехніка”
Кафедра ЕОМ
Лабораторна робота №1
з диципліни: «Паралельні і розподілені обчислення»
на тему: «ВИКОРИСТАННЯ ФУНКЦІОНАЛЬНОЇ ДЕКОМПОЗИЦІЇ ДЛЯ РОЗВ’ЯЗКУ ОБЧИСЛЮВАЛЬНИХ ЗАДАЧ»
МЕТА РОБОТИ. Вивчити методи декомпозицій задач. Набути навиків розв’язування задач з використанням функціональної декомпозиції.
Завдання:
Вираз, який слід обрахувати, заданий наступним чином:
2
матриця
Вектор y1: bi=1/(i2-2i+3) для парних і
bi=i для непарних і
Вектор y2 (3A1b1’+2A1c1’)’
Матриця Y3
A2C2-B2A 2
Cij=1/(i+j)
Послідовність виконання.
1. Аналіз завдання.
Для заданого виразу вхідними даними є:
розмірність матриць – n;
матриці ;
вектори-стовпці .
Ці параметри повинні вводитися з клавіатури, або генеруватися випадковим чином (крім розмірності). При чому, елементи всіх матриць та векторів є цілими додатними числами, більшими за нуль.
Вектор-стовпець та матриця обраховуються, виходячи з уведеної розмірності, зауважимо, що значення їх елементів завжди менші одиниці і різко спадають зі збільшенням розмірності.
Наприклад для n=3, значення вектора-стовпця будуть становити:
b1 = 1; b2 = 1/(22 – 2*2 + 3) = 0.3; b3 = 3;
а значення матриці , відповідно:
C11=1/(1+1)=0.5 C12=1/(1+2)=0,33 C13=1/(1+3)=0,25
C21=1/(2+1)=0,33 C22=1/(2+2)=0,25 C23=1/(2+3)=0,2
C31=1/(3+1)=0,25 C32=1/(3+2)=0,2 C33=1/(3+3)=0,16
При утворенні враховуємо, що результатом множення матриці А на вектор-стовпець b є вектор-стовпець, елементи якого будуть раціональними числами(тобто матимуть значущу дробову частину).
При утворенні враховуємо, що результатом додавання двох векторів-стовпців є вектор-стовпець, елементи якого можуть бути більшими за нуль цілими числами. Далі, при множенні цілочисельної додатної матриці А1 на результат додавання, отримаємо вектор-стовпець з цілочисельними елементами.
При утворенні враховуємо, що присутні лише операції віднімання та множення, а тому вихідний результат може бути додатнім або відємним і завжди матиме значущу дробову частину.
Таким чином, згідно поставленої задачі, в обчисленні загального виразу приймають участь три різні елементи – два вектори стовпці та матриця .
Перший множник загального виразу містить два доданки – y2(y1) матрицю і y2y1. Оскільки, згідно правил матричних обчислень, добуток не є комутативною операцією, всі множення слід виконувати в тій послідовності, яка задана, вищий пріоритет мають тільки множники які знаходяться в дужках, вони виконуються першими. Результатом множення матриці на вектор-стовпець буде вектор стовпець. Наступним кроком, буду множення отриманого вектора-стовпця на рядок y2. Отже, після множень рядків і стовпців та їх додавання отримаємо число у лівому загальному множнику.
Другий множник складається з додавання матриці Y3 в квадраті і матриці, яка є результатом множення y1 на y2.
При множенні цих двох множників в результаті отримаємо матрицю.
Таким чином, з попереднього випливає, що остаточний результат є матриця, елементи якого можуть бути як додатними так і від’ємними і завжди мають дробову частину.
2. Декомпозиція задачі.
Однозначно, всі обчислення безпосередньо залежать від розмірності даних, тому найперше, слід забезпечити ввід змінної n, що визначає цю розмірність. Далі, можна паралельно виконувати обчислення значень вектора b та матриці С2, оскільки вони незалежні від інших параметрів. Крім того, на тому ж рівні декомпозиції слід визначати вхідні дані, тобто вводити з клавіатури, або генерувати випадковим чином матриці та вектори-стовпці . Наступний рівень декомпозиції – це знаходження елементів виразу. Значення залежить від введеної матриці А та обрахованого вектора b. Значення залежить від введеної А1 та векторів b1 і c1. Зауважимо, що множення на константу не є окремою операцією, як і транспонування векторів. Аналогічно, знаходимо . Подальша декомпозиція відбувається згідно заданої послідовності операцій та врахування залежностей отриманих на кожному рівні даних. Повна схема декомпозиції обчислення заданого виразу приведена нижче.
3. Об’єднання частин виразу проведено безпосередньо у схемі декомпозиції, оскільки воно однозначно визначається порядком обчислень.
4. Для написання програми, що ілюструє процес обчислення виразу згідно розробленої схеми декомпозиції, слід врахувати наступні особливості:
Дані, що вводяться з клавіатури, або генеруються випадковим чином повинні бути цілими числами, більшими за нуль. Результати проміжних обрахунків будуть містити дробову частину, виняток складає лише елемент y2. Тому слід обирати відповідний тип даних(багатобайтний).
Оскільки на окремо взятому рівні декомпозиції обраховуються незалежні частини підвиразів, функції що їх програмно реалізують повинні викликатися псевдо-одночасно.(Тобто перш ніж виконувати будь яку функцію третього рівня, слід виконати всі функції другого рівня і т.д.)
Схема декомпозиції обчислення виразу
5. Текст програми
package com.kostyabakay.concurrencylab; import android.os.Bundle; import android.support.v7.app.AppCompatActivity; import android.support.v7.widget.Toolbar; import android.view.View; import android.view.Menu; import android.view.MenuItem; import android.widget.ArrayAdapter; import android.widget.Button; import android.widget.Spinner; import android.widget.TextView; import java.util.Random; public class MainActivity extends AppCompatActivity { Spinner matrixOrderSpinner; Button generateAndCalculateButton; TextView matrixAOutput, matrixA1Output, columnB1Output, columnC1Output, matrixA2Output, matrixB2Output, matrixCOutput, resultOutput, calculationColumnBOutput, calculationColumnY1Output, calculationRowY2Output, calculationMatrixY3Output, calculationColumnY3Y1Output, calculationNumberY2Y3Y1Output, calculationNumberY2Y1Output, calculationLeftBracketOutput, calculationMatrixY3InSquareOutput, calculationMatrixY1Y2Output, calculationRightBracketOutput; int matrixOrder; int[][] matrixA, matrixA1, matrixA2, matrixB2, matrixC, Y3, result; int[] b, y1, y2, columnB1, columnC1; @Override protected void onCreate(Bundle savedInstanceState) { super.onCreate(savedInstanceState); initUI(); } private void initUI() { setContentView(R.layout.activity_main); Toolbar toolbar = (Toolbar) findViewById(R.id.toolbar); setSupportActionBar(toolbar); // --------------------------------- Spinner --------------------------------------- matrixOrderSpinner = (Spinner) findViewById(R.id.matrix_order_spinner); // Create an ArrayAdapter using the string array and a default spinner layout ArrayAdapter<CharSequence> adapter = ArrayAdapter.createFromResource(this, R.array.matrix_order_spinner, android.R.layout.simple_spinner_item); // Specify the layout to use when the list of choices appears adapter.setDropDownViewResource(android.R.layout.simple_spinner_dropdown_item); // Apply the adapter to the spinner matrixOrderSpinner.setAdapter(adapter); // matrixOrderString = matrixOrderSpinner.getSelectedItem().toString(); // int matrixOrder = Integer.parseInt(matrixOrderString); generateAndCalculateButton = (Button) findViewById(R.id.generate_and_calculate_button); matrixAOutput = (TextView) findViewById(R.id.matrixA_output); matrixA1Output = (TextView) findViewById(R.id.matrixA1_output); columnB1Output = (TextView) findViewById(R.id.column_b1_output); columnC1Output = (TextView) findViewById(R.id.column_c1_output); matrixA2Output = (TextView) findViewById(R.id.matrixA2_output); matrixB2Output = (TextView) findViewById(R.id.matrixB2_output); matrixCOutput = (TextView) findViewById(R.id.matrixC_output); calculationColumnBOutput = (TextView) findViewById(R.id.calculation_column_b_output); calculationColumnY1Output = (TextView) findViewById(R.id.calculation_column_y1_output); calculationRowY2Output = (TextView) findViewById(R.id.calculation_row_y2_output); calculationMatrixY3Output = (TextView) findViewById(R.id.calculation_matrix_Y3_output); calculationColumnY3Y1Output = (TextView) findViewById(R.id.calculation_column_Y3y1_output); calculationNumberY2Y3Y1Output = (TextView) findViewById(R.id.calculation_number_y2Y3y1_output); calculationNumberY2Y1Output = (TextView) findViewById(R.id.calculation_number_y2y1_output); calculationLeftBracketOutput = (TextView) findViewById(R.id.calculation_number_left_bracket_output); calculationMatrixY3InSquareOutput = (TextView) findViewById(R.id.calculation_matrix_Y3_in_square_output); calculationMatrixY1Y2Output = (TextView) findViewById(R.id.calculation_matrix_y1y2_output); calculationRightBracketOutput = (TextView) findViewById(R.id.calculation_matrix_right_bracket_output); resultOutput = (TextView) findViewById(R.id.calculation_result_output); generateAndCalculateButton.setOnClickListener(new View.OnClickListener() { @Override public void onClick(View v) { generateAndCalculateButton.setClickable(false); generateAndCalculateButton.setText("Згенеровано і обраховано"); String matrixOrderString = matrixOrderSpinner.getSelectedItem().toString(); int mo = Integer.parseInt(matrixOrderString); matrixOrder = mo; matrixA = generateMatrixA(mo); matrixA1 = generateMatrixA1(matrixOrder); columnB1 = generateColumnB1(matrixOrder); columnC1 = generateColumnC1(matrixOrder); matrixA2 = generateMatrixA2(matrixOrder); matrixB2 = generateMatrixB2(matrixOrder); matrixC = generateMatrixC(matrixOrder); calculate(); } }); } private int[][] generateMatrixA(int order) { int n = order; int[][] matrixA = new int[n][n]; Random random = new Random(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { matrixA[i][j] = random.nextInt(10); matrixAOutput.append(String.valueOf(matrixA[i][j]) + " "); } matrixAOutput.append("\n"); } return matrixA; } private int[][] generateMatrixA1(int order) { int n = order; int[][] matrixA1 = new int[n][n]; Random random = new Random(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { matrixA1[i][j] = random.nextInt(10); matrixA1Output.append(String.valueOf(matrixA1[i][j]) + " "); } matrixA1Output.append("\n"); } return matrixA1; } private int[] generateColumnB1(int order) { int n = order; int[] columnB1 = new int[n]; Random random = new Random(); for (int i = 0; i < n; i++) { columnB1[i] = random.nextInt(10); columnB1Output.append(String.valueOf(columnB1[i]) + "\n"); } return columnB1; } private int[] generateColumnC1(int order) { int n = order; int[] columnC1 = new int[n]; Random random = new Random(); for (int i = 0; i < n; i++) { columnC1[i] = random.nextInt(10); columnC1Output.append(String.valueOf(columnC1[i]) + "\n"); } return columnC1; } private int[][] generateMatrixA2(int order) { int n = order; int[][] matrixA2 = new int[n][n]; Random random = new Random(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { matrixA2[i][j] = random.nextInt(10); matrixA2Output.append(String.valueOf(matrixA2[i][j]) + " "); } matrixA2Output.append("\n"); } return matrixA2; } private int[][] generateMatrixB2(int order) { int n = order; int[][] matrixB2 = new int[n][n]; Random random = new Random(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { matrixB2[i][j] = random.nextInt(10); matrixB2Output.append(String.valueOf(matrixB2[i][j]) + " "); } matrixB2Output.append("\n"); } return matrixB2; } private int[][] generateMatrixC(int order) { int n = order; int[][] matrixC = new int[n][n]; Random random = new Random(); for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { matrixC[i][j] = random.nextInt(10); matrixCOutput.append(String.valueOf(matrixC[i][j]) + " "); } matrixCOutput.append("\n"); } return matrixC; } private void calculate() { b = calc_b(); y1 = calc_y1(matrixA, matrixOrder); y2 = calc_y2(matrixA1, columnB1, columnC1, matrixOrder); Y3 = calc_Y3(matrixA2, matrixB2, matrixC, matrixOrder); result = calc_result(y1, y2, Y3, matrixOrder); } private int[] calc_b() { b = new int[matrixOrder]; // Заповнення вектора b значеннями for (int i = 0; i < matrixOrder; i++) { if (i % 2 == 0) { b[i] = 1 / (i * i - 2 * i + 3); } else { b[i] = i; } calculationColumnBOutput.append(String.valueOf(b[i]) + "\n"); } return b; } private int[] calc_y1(int[][] matrixA, int matrixOrder) { y1 = new int[matrixOrder]; // Обрахування вектора-стовпця y1 for (int i = 0; i < matrixOrder; i++) { for (int j = 0; j < matrixOrder; j++) { y1[i] += matrixA[i][j] * b[j]; } calculationColumnY1Output.append(String.valueOf(y1[i]) + "\n"); } return y1; } private int[] calc_y2(int[][] matrixA1, int[] b1, int[] c1, int matrixOrder) { y2 = new int[matrixOrder]; int[] y2part1 = new int[matrixOrder]; int[] y2part2 = new int[matrixOrder]; int[] b1Transponated = new int[matrixOrder]; int[] c1Transponated = new int[matrixOrder]; for (int i = 0; i < matrixOrder; i++) { b1Transponated[i] = b1[i]; } for (int i = 0; i < matrixOrder; i++) { c1Transponated[i] = c1[i]; } // Обрахування вектора-стовпця y2part1 for (int i = 0; i < matrixOrder; i++) { for (int j = 0; j < matrixOrder; j++) { if (i == j) { y2part1[i] += 3 * matrixA1[i][j] * b1Transponated[i]; } } } // Обрахування вектора-стовпця y2part1 for (int i = 0; i < matrixOrder; i++) { for (int j = 0; j < matrixOrder; j++) { if (i == j) { y2part2[i] += 2 * matrixA1[i][j] * c1Transponated[i]; } } } // Обрахування вектора-рядка y2 for (int i = 0; i < matrixOrder; i++) { y2[i] = y2part1[i] + y2part2[i]; calculationRowY2Output.append(String.valueOf(y2[i]) + " "); } return y2; } private int[][] calc_Y3(int[][] matrixA2, int[][] matrixB2, int[][] matrixC, int matrixOrder) { Y3 = new int[matrixOrder][matrixOrder]; int[][] Y3part1 = new int[matrixOrder][matrixOrder]; int[][] Y3part2 = new int[matrixOrder][matrixOrder]; // Y3part1 for (int i = 0; i < matrixOrder; i++) { for (int j = 0; j < matrixOrder; j++) { Y3part1[i][j] += matrixA2[i][j] * matrixC[i][j]; } } // Y3part2 for (int i = 0; i < matrixOrder; i++) { for (int j = 0; j < matrixOrder; j++) { Y3part2[i][j] += matrixB2[i][j] * matrixA2[i][j]; } } // Y3 for (int i = 0; i < matrixOrder; i++) { for (int j = 0; j < matrixOrder; j++) { Y3[i][j] = Y3part1[i][j] - Y3part2[i][j]; calculationMatrixY3Output.append(String.valueOf(Y3[i][j] + " ")); } calculationMatrixY3Output.append("\n"); } return Y3; } private int[][] calc_result(int[] y1, int[] y2, int[][] Y3, int matrixOrder) { int[] Y3y1 = new int[matrixOrder]; int y2Y3y1 = 0; int y2y1 = 0; int[][] Y3Y3 = new int[matrixOrder][matrixOrder]; int[][] y1y2 = new int[matrixOrder][matrixOrder]; int part1 = 0; int[][] part2 = new int[matrixOrder][matrixOrder]; int[][] result = new int[matrixOrder][matrixOrder]; // Обрахування вектора-стовпця Y3y1 for (int i = 0; i < matrixOrder; i++) { int sum = 0; for (int j = 0; j < matrixOrder; j++) { sum = sum + Y3[i][j] * y1[j]; } Y3y1[i] = sum; calculationColumnY3Y1Output.append(String.valueOf(Y3y1[i]) + "\n"); } // Обрахування числа y2Y3y1 for (int i = 0; i < matrixOrder; i++) { for (int j = 0; j < matrixOrder; j++) { if (i == j) { y2Y3y1 += y2[i] * Y3y1[j]; } } } calculationNumberY2Y3Y1Output.append(String.valueOf(y2Y3y1)); // Обрахування числа y2y1 for (int i = 0; i < matrixOrder; i++) { for (int j = 0; j < matrixOrder; j++) { if (i == j) { y2y1 += y2[i] * y1[j]; } } } calculationNumberY2Y1Output.append(String.valueOf(y2y1)); part1 = y2Y3y1 + y2y1; // Обрахування числа у лівих дужках calculationLeftBracketOutput.append(String.valueOf(part1)); // Обрахування матриці Y3 в квадраті for (int i = 0; i < matrixOrder; i++) { for (int j = 0; j < matrixOrder; j++) { Y3Y3[i][j] += Y3[i][j] * Y3[i][j]; calculationMatrixY3InSquareOutput.append(String.valueOf(Y3Y3[i][j] + " ")); } calculationMatrixY3InSquareOutput.append("\n"); } // Обрахування матриці y1y2 for (int i = 0; i < matrixOrder; i++) { for (int j = 0; j < matrixOrder; j++) { y1y2[i][j] += y1[i] * y2[j]; calculationMatrixY1Y2Output.append(String.valueOf(y1y2[i][j] + " ")); } calculationMatrixY1Y2Output.append("\n"); } // Обрахування матриці, яка є другою частиною виразу for (int i = 0; i < matrixOrder; i++) { for (int j = 0; j < matrixOrder; j++) { part2[i][j] = Y3Y3[i][j] + y1y2[i][j]; calculationRightBracketOutput.append(String.valueOf(part2[i][j] + " ")); } calculationRightBracketOutput.append("\n"); } // Обрахування і вивід загального виразу for (int i = 0; i < matrixOrder; i++) { for (int j = 0; j < matrixOrder; j++) { result[i][j] = part1 * part2[i][j]; resultOutput.append(String.valueOf(result[i][j]) + " "); } resultOutput.append("\n"); } return result; }
6. Результати виконання програми
Висновки
В роботі використано паралелізм на рівні підзадач, оскільки передбачається, що кожен блок зі схеми декомпозиції є реалізований у виді функції. Це є середньоблоковий паралелізм. Обмін даними відбувається через використання спільних змінних. Присутня залежність даних між різними рівнями декомпозиції, але в межах одного рівня її немає. Є залежність за керуванням, оскільки послідовність обчислювального процесу наперед однозначно відома. Залежність за ресурсами та вводом/виводом може бути визначена лише у відношенні до певної обчислювальної системи.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора