Скачать 475.48 Kb.
|
ВІДКРИТИЙ МІЖНАРОДНИЙ УНІВЕРСИТЕТ РОЗВИТКУ ЛЮДИНИ “УКРАЇНА” ЛАБОРАТОРНА РОБОТА №2 " АЛГОРИТМИ ПАРАЛЕЛЬНИХ ОБЧИСЛЕНЬ " з дисципліни " Методи паралельних обчислень " спеціальності " Програмне забезпечення автоматизованих систем " Виконав студент 3 курсу групи ПА-21 ______________ Докукін Є.В. (підпис) (Прізвище І.Б.) "____"____________ 2005 р. ЗАРАХОВАНО Викладач ________________ Доля В.Г. "____"____________ 200__ р. Київ Університет "Україна" 2005 СОДЕРЖАНИЕ 1.1.Реферат 2 1. Лабораторная работа №2 " Алгоритмы параллельных вычислений " Цель работы – приобретение практических навыков построения и применения алгоритмов параллельных вычислений. Обработка информации в параллельных и распределенных вычислительных системах осуществляется одновременно на многих параллельных вычислительных машинах (ПВМ). Для реализации алгоритма вычислений на ПВМ необходимо представить его в виде последовательности групп операций. Все операции одной группы должны быть независимыми и обладать возможностью быть выполненными одновременно (параллельно) на имеющихся функциональных устройствах ПВМ. Представление алгоритма решения задачи в виде упорядоченных групп вычислительных операций, выполняемых в определенной последовательности, называется параллельной формой алгоритма (ПФ). Каждая группа операций называется ярусом ПФ (шагом алгоритма), число групп – высотой ПФ, максимальное число операций в ярусе – шириной ПФ. Высота определяет число шагов алгоритма, а ширина – число процессоров ПВМ, необходимых для решения задачи. Основными характеристиками параллельных алгоритмов являются следующие: 1) Высота алгоритма h отражает время выполнения алгоритма. Если исходная задача определяется n входными переменными, то высота ПФ определяется соотношением: h log2n. 2) Ширина алгоритма l – равна количеству процессоров. 3) Ускорение Sp алгоритма показывает, во сколько раз быстрее он решает задачу по сравнению с лучшим из последовательных алгоритмов решения той же задачи на однопроцессорной вычислительной машине (ВМ), и определяется соотношением: Sp = T1 / Tp , 1 ≤ Sp ≤ p, где: T1 – число операций, необходимое для решения задачи на однопроцессорной ВМ; Tp – то же – на ПВМ с p процессорами. 4) Эффективность алгоритма определяет загруженность процессоров и представляет собой ускорение алгоритма, достигнутое по отношению к одному процессору. Т.е. величина данная характеризуется отношением числа выполненных алгоритмом операций к числу возможных операций, которые можно выполнить за то же время: Ep = Sp / p, 1/p ≤ Ep ≤ 1. 5) Устойчивость алгоритма к ошибкам округления. Параллельные алгоритмы решения задач алгебры с высотами порядка log22n являются сильно неустойчивыми к влиянию ошибок округления и без радикального изменения они не могут быть использованы в больших ПВМ. 6) Конфликтность алгоритма определяет состояние, когда несколько процессоров в процессе вычислений выбирают в памяти одну и ту же информацию, т.е. возникает конфликтная ситуация. Конфликтность алгоритма можно устранить путем увеличения его высоты, устанавливая для процессоров очередность доступа к информации. Графовые модели параллельных вычислений Графом называется геометрическая фигура, состоящая из вершин (точек, узлов) и линий между ними, которые называются дугами (ребрами) графа. Формализованную модель предметной области решаемой задачи можно представить в виде ориентированного графа, вершины которого – выполняемые операции, а дуги – информационные связи между операциями. Решение задачи сводится к нахождению вершины (или множества вершин) и (или) ребра (множества ребер), удовлетворяющим определенным условиям. Одной из основных задач параллельных вычислений является анализ особенностей графов алгоритмов с целью определения возможности их распараллеливания и выявления параллельных ветвей. Графовые модели параллельных алгоритмов в памяти ПВМ обычно представляют в виде двух матричных форм, к которым относятся:
1.2. Построение параллельной формы алгоритма решения задачи перемножения двух прямоугольных матриц 1.2.1 Постановка задачи
Матрица А[7,7]
|
Методы и средства организации обработки потоковой информации на распределенных... Специальность 05. 13. 11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей | Нир: “разработка алгоритмов поиска глобальных экстремумов при наличии... Федеральное Государственное бюджетное образовательное учреждение высшего профессионального образования “Саратовский государственный... | ||
Тема: «Аксиома параллельных прямых» Цель урока: закрепить признаки параллельных прямых, свойства параллельных прямых и аксиому параллельных прямых | Реферат в связи с большими объемами перерабатываемой информации в... Цель работы – приобретение практических навыков распараллеливания процесса вычислений при решении вычислительных задач большой размерности... | ||
«Реализация фгос на уроках математики: нетрадиционные уроки» Цель урока: закрепить признаки параллельных прямых, свойства параллельных прямых и аксиому параллельных прямых | Календарно-тематическое планирование учебного материала Цель урока: закрепить признаки параллельных прямых, свойства параллельных прямых и аксиому параллельных прямых | ||
Дидактические: 1 продолжить формирование зун по теме «параллельные прямые» Цель урока: закрепить признаки параллельных прямых, свойства параллельных прямых и аксиому параллельных прямых | Г. Н. Флерова «утверждаю» Директор Н. Г. Кренделева Приказ от «30»августа... Цель урока: закрепить признаки параллельных прямых, свойства параллельных прямых и аксиому параллельных прямых | ||
Методические рекомендации по изучению дисциплины теория и методика... Цель урока: закрепить признаки параллельных прямых, свойства параллельных прямых и аксиому параллельных прямых | Рабочая программа составлена в соответствии с требованиями федерального... Цель урока: закрепить признаки параллельных прямых, свойства параллельных прямых и аксиому параллельных прямых | ||
Конспект урока решение задач по теме «Параллельные прямые» (Тема урока) фио (полностью) Цель урока: закрепить признаки параллельных прямых, свойства параллельных прямых и аксиому параллельных прямых | Методы решения задач с переменной интенсивностью потоков данных на... Специальность 05. 13. 11 Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей | ||
Лекция № Тема: логические основы ЭВМ В вычислительных машинах коды нуля и единицы представляются электрическими сигналами, имеющими два различных состояния. Наиболее... | Рабочая программа учебной дисциплины вычислительные системы Целью курса «Вычислительные системы» является изучение общих сведений о многопроцессорных вычислительных системах, включая их назначение,... | ||
Диплом разработка и исследование информационных моделей шифратора и дешифратора Во многих устройствах, в том числе и в электронно-вычислительных машинах (эвм), используются кодированные сигналы или коды. Кодом... | Программа по формированию навыков безопасного поведения на дорогах... Знать: определение параллельных прямых в пространстве. Уметь: анализировать в простейших случаях взаимное расположение прямых в пространстве,... |