Национальный Исследовательский Университет

МОСКОВСКИЙ ЭНЕРГЕТИЧЕСКИЙ ИНСТИТУТ

Институт автоматики и вычислительной техники

Кафедра прикладной математики

Лабораторная работа № 5

Программирование на языке FPTL

Курс «Параллельные системы и параллельные вычисления»

Выполнил

студент 5 курса группы А-13-08

Захаров Антон

Преподаватель

Шамаль Павел Николаевич

Постановки задач

1. Пусть дана квадратная матрица размерности . Требуется реализовать алгоритм нахождения определителя. Матрицу представлять в виде списка списков.

2. Нахождение простых чисел Мерсе́нна (вида ).

Для решения поставленных задач необходимо составить рекурсивные программы на языке FPTL, а также исследовать характеристики разработанных программ в зависимости от числа потоков.

Тестирование проводилось на компьютере со следующей конфигурацией:

ПРОЦЕССОР Intel Core i5 2500MHz Ivy Bridge

ОПЕРАТИВНАЯ ПАМЯТЬ 16Gb DDR3 1600MHz

ФИЗИЧЕСКИЙ НАКОПИТЕЛЬ OCZ-VERTEX3 (120Gb, SATA600, SSD)

ГРАФИЧЕСКИЙ ПРОЦЕССОР AMD Radeon HD 7700 (1Gb DDR5 4.6GHz)

ОПЕРАЦИОННАЯ СИСТЕМА Windows 7 Ultimate x64 (SP1)

Задача 1

Разложение по строке (сложность )

Определитель (или детерминант) – одно из основных понятий линейной алгебры. Определитель матрицы является многочленом от элементов квадратной матрицы.

Для матрицы первого порядка детерминантом является сам единственный элемент этой матрицы:

Для матрицы детерминант определяется как:

Для матрицы определитель задаётся рекурсивно:

где — дополнительный минор к элементу . Эта формула называется разложением по строке.

В частности, формула вычисления определителя матрицы такова:

Для решения данной задачи на языке FPTL был определён вспомогательный тип List, значениями которого могут быть пустой список (c_nil) или элемент любого типа и список List из элементов этого типа. Для удобства работы со списком были написаны рекурсивные функции removeFromList и listGet, осуществляющие удаление и получение элементов списка с заданным индексом.

Чтение матрицы из файла осуществляется набором рекурсивных функций:
readNumb, считывающей число из файла, используя регулярное выражение,
readLine, считывающей строку в список элементов, readElems и readMatrix.

Для облечения работы с матрицей (списком списков) также была реализована рекурсивная функция get для получения элемента матрицы с заданным индексом.

Результаты вычислительного эксперимента

Матрица 10 х 10

Число потоков	Время решения (сек)						Время решения1 (сек)		Ускорение
	1	2	3	4	5
1	52,373	52,860	52,514	52,653	52,979	52,676		1,000
2	38,168	38,249	38,042	37,834	37,955	38,050		1,384
3	32,085	31,763	31,584	31,215	31,062	31,542		1,670
4	29,718	29,854	29,716	29,765	29,810	29,773		1,769
5	35,885	39,602	38,685	37,520	39,301	38,199		1,379
6	40,587	40,602	39,227	39,111	41,202	40,146		1,312
7	39,988	40,420	39,351	39,256	40,056	39,814		1,323
8	41,771	42,413	42,171	41,614	42,069	42,008		1,254
9	51,488	51,168	52,249	51,042	51,834	51,556		1,022
10	67,732	67,085	67,763	65,584	66,215	66,876		0,788
11	71,582	74,718	70,854	68,716	69,765	71,127		0,741
12	85,287	81,614	92,988	104,420	89,351	90,732		0,581

Время

(сек)

Зависимость времени решения задачи от числа потоков

Число

потоков

Ускорение

Зависимость ускорения параллельного решения от числа потоков

Число

потоков

Data List['t]

{

List = c_nil ++ 't * List['t].c_cons;

}

// Вычисление определителя матрицы из файла

// in [1] - путь к файлу с матрицей

Scheme Determinant

{

@ = [1].readMatrix.det.print;

// Вычисление определителя матрицы

// in [1] - матрица

// in [2] - размерность матрицы

det = (id * 1).det1;

// in [3] - индекс текущего столбца

// out [1] - определитель матрицы

det1 = ([2] * 1).equal -> [1].~c_cons.[1].~c_cons.[1],

([2] * [3]).equal -> id.det1i,

(id.det1i * ([1] * [2] * [3].inc).det1).add;

det1i = ([3].inc.sign * ([1] * 1 * [3]).get * id.minor).mul3;

// Вычисление дополнительного минора к заданному элементу 1-ой строки матрицы

// in [1] - матрица

// in [2] - размерность матрицы

// in [3] - индекс столбца элемента

// out [1] - дополнительный минор

minor = (([1] * [2] * 1 * [3]).submatr * [2].dec).det;

// Получение подматрицы

// in [1] - матрица

// in [2] - размерность матрицы

// in [3] - номер удаляемой строки

// in [4] - номер удаляемого столбца

submatr = (id * 1).submatr1;

// in [5] - номер текущей строки

// out [1] - подматрица

submatr1 = ([5] * [2]).greater -> c_nil,

([5] * [3]).equal ->

([1].~c_cons.[2] * [2] * [3] * [4] * [5].inc).submatr1,

(([1].~c_cons.[1] * [2] * [4] * 1).removeFromList *

([1].~c_cons.[2] * [2] * [3] * [4] * [5].inc).submatr1).c_cons;

// --- Вспомогательные функции ---

// Удаление элемента из списка

// in [1] - список

// in [2] - количество элементов списка

// in [3] - индекс удаляемого элемента списка

// in [4] - индекс текущего элемента

// out [1] - новый список

removeFromList = ([4] * [2]).greater -> c_nil,

([4] * [3]).equal ->

([1].~c_cons.[2] * [2] * [3] * [4].inc).removeFromList,

([1].~c_cons.[1] * ([1].~c_cons.[2] * [2] * [3] *

[4].inc).removeFromList).c_cons;

// Считывание матрицы и её размерности из файла

// in [1] - файловая переменная

// out [1] - матрица

// out [2] - размерность матрицы

readMatrix = [1].readFile.readNumb.(([2] * [1]).readElems * [1]);

// Считывание матрицы из файла

// in [1] - строка

// in [2] - количество элементов в строке

// out [1] - матрица

readElems = ([1] * "").equal -> c_nil,

(([1] * [2] * 0).readLine * [2]).([1] * ([2] * [3]).readElems).c_cons;

// Чтение строки в список элементов

// in [1] - строка

// in [2] - размерность матрицы

// in [3] - индекс текущего столбца

// out [1] - прочитанный список

// out [2] - оставшаяся часть строки

readLine = ([2] * [3]).equal -> c_nil * [1],

(([1].readNumb * [2] * [3]).([1] * ([2] * [3] *

[4].inc).readLine)).(([1] * [2]).c_cons * [3]);

// Считывание числа из файла

// in [1] - строка матрицы

// out [1] - первое число, находящееся в строке

// out [2] - оставшаяся часть строки

readNumb = ([1] * "-?\\d+").getToken.([1].toInt * [2]);

// Получение элемента матрицы

// in [1] - матрица

// in [2] - индекс строки

// in [3] - индекс столбца

// out [1] - элемент матрицы

get = (([1] * [2]).listGet * [3]).listGet;

// Получение элемента списка

// in [1] - список

// in [2] - индекс элемента списка

listGet = ([1] * [2] * 1).listGet1;

// in [3] - индекс текущего элемента списка

// out [1] - элемент списка

listGet1 = ([2] * [3]).equal -> [1].~c_cons.[1],

([1].~c_cons.[2] * [2] * [3].inc).listGet1;

// Умножение [1]x[2]x[3]

mul3 = ([1] * ([2] * [3]).mul).mul;

// Возвращает 1, если [1] - чётное, иначе возвращает -1

sign = (([1] * 2).mod * 0).equal -> 1, -1;

// Инкремент

inc = ([1] * 1).add;

// Декремент

dec = ([1] * 1).sub;

}

Application

% Determinant("G10.txt")

Задача 2

Числа Мерсенна – числа вида , где – натуральное число.

Последовательность чисел Мерсенна начинается так:

1, 3, 7, 15, 31, 63, 127, 255, 511, 1023, …

Числа Мерсенна получили известность в связи с эффективным критерием простоты Люка – Лемера, благодаря которому простые числа Мерсенна давно удерживают лидерство как самые большие известные простые числа. На данный момент самым большим известным простым числом является число Мерсенна .