КАФЕДРА ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ

ТЕМЫ

КУРСОВЫХ (ДИПЛОМНЫХ) РАБОТ

СПбГУ

СПИСОК ТЕМ КУРСОВЫХ И ДИПЛОМНЫХ РАБОТ

Тема № 1

DS-линки и маршрутизаторы

Тема № 2

Распараллеливание при LU-факторизации

Тема № 3

Параллельное программирование с использованием интерфейса MPI в одномерной краевой задаче Тема № 4 Распараллеливание при вычислении квадратур Тема № 5 Метод конечных элементов на параллельной системе Тема № 6 Распараллеливание процесса триангуляции двумерной области Тема № 7 Построение симплициального подразделения цилиндрической области с использованием параллельной системы Тема № Распараллеливание МКЭ для одной нестационарной задачи Тема № Распараллеливание вычислений тригонометрических функций Тема № Распараллеливание вычислений экспоненциальной и логарифмической функций Тема № Распараллеливание вычислений обратных тригонометрических функций Тема № Распараллеливание вычислений обратных гиперболических функций Тема № Быстрое преобразование Фурье и его распараллеливание Тема № Распараллеливание вычислений минимальных полиномиальных сплайнов Тема № Вычисление МКЭ-аппроксимаций с помощью параллельных систем Тема № Введение в стандарт MPI-2; основные направления модификации Тема № Защита данных в MPI- Тема № PVM параллельная виртуальная машина и методы реализации параллельных программ Тема № 19 (для II курса) Составление экспертного заключения по одному (по выбору студента) из языков программирования: Fortran 90, Ada 95, C++, Java Тема № 20 (для III курса) Написание лексического анализатора для нового языка программирования Тема № 21 (для III курса) Написание синтаксического анализатора для нового языка программирования Тема № 22 (для IV курса) Написание семантического анализатора для нового языка программирования Тема № 23 (для IV курса) Написание подсистемы вызова функций времени компиляции Тема № 24 (дипломная работа) Написание подсистемы ввода-вывода для стандартной библиотеки Тема № Многоядерные архитектуры и распараллеливание Тема № Оценка эффективности работы параллельных процессоров при реализации простых вычислительных алгоритмов Тема № Приведение подобных членов в системах аналитических вычислений Тема № Метод SOR при распараллеливании численного решения эллиптических задач Тема № Применение стандарта MPI в методе Монте-Карло Организация параллельных процессов для динамических параллельных вычислений Введение в стандарт MPI-2: основные направления модификаций Сравнение MPI и Open MP: преимущества и недостатки

КАФЕДРА ПАРАЛЛЕЛЬНЫХ АЛГОРИТМОВ

ПОДРОБНОЕ ОПИСАНИЕ

НЕКОТОРЫХ ИЗ ПРЕДЛАГАЕМЫХ ТЕМ

КУРСОВАЯ (ДИПЛОМНАЯ) РАБОТА

Введение в проблему Для решения сверхсложных задач соэдаются высокопроизводительные вычислительные системы. Современные технологии сохдания процессоров не позволяют в дальнейшем существенно наращивать их быстродействие. Поэтому основное направлением в разработке новых высокопроизводительных ВС является увеличение числа параллельно работающих процессоров.

Узким местом параллельных систем являются коммуникационные среды. Последние зачастую создаются на базе транспьютеров, которые на момент их создания являлись наиболее производительными микропроцессорами, совмещающими в одном кристалле процессор, память и связующие каналы. Со временем появились значительно более производительные процессоры, однако, транспьютеры не утратили своих позиций при создании коммуникационных сред. Узким местом транспьютеров первого поколения были OS-линки, которые можно было использовать лишь для связи двух процессов, протекающих в передающем и принимающем транспьютерах. На смену им пришли DS-линки, значительно расширяющие возможности коммуникаций.

Постановка задачи Требуется 1) ознакомиться с основами стандартов OS-линков и DS-линков, дать их сравнительный анализ (см. [1], с. 70-77), 2) изучить характеристики и функционирование транспьютера T (см. [2]), 3) подобрать литературу по использованию транспьютерных систем (в библиотеке, по реферативным журналам и в Интернете), 4) построить модель транспьютерной параллельной системы, дать ее программную реализацию, провести отладку и тестирование программы Ожидаемые результаты Курсовая работа должна содержать подробную разработку пунктов 1) и 2) предложенного задания В дипломной работе (продолжение курсовой) следует реализовать пункты 3) – 4). Полученные теоретические результаты следует проиллюстрировать на работающих программах для параллельного кластера.

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

[1] Корнеев В.В. Параллельные вычислительные системы. Москва.

1999.

[2] The T9000 transputer. Immos. SGS-Thomson Microelectronics Group.

1991. 194 p.

КУРСОВАЯ (ДИПЛОМНАЯ) РАБОТА

"Распараллеливание при LU-факторизации" Введение в проблему LU -факторизация (см. [1], с. 39-47) квадратной матрицы A порядка n состоит в представлении этой матрицы в виде произведения A = LU нижнетреугольной матрицы L с единицами на главной диагонали на верхнетреугольную матрицу U (иногда рассматривают U L-факторизацию).

Такая факторизация применяется для различных целей, и, в частности, при решении большого числа систем линейных алгебраических уравнений с одной и той же матрицей. Распараллеливание LU -факторизации в зависимости от рассматриваемой параллельной вычислительной системы (ПВС) является весьма важной задачей. ПВС обычно снабжена интерфейсом для параллельного программирования; чаще всего это широко известный интерфейс MPI Message Passing Interface (см., например, [2], с. 153-159).

Постановка задачи Требуется разработать теоретические аспекты распараллеливания LU факторизации, а именно, в некоторых условных единицах нужно оценить необходимый объем памяти и необходимое число тактов при определенных предположениях о параллельной системе и о характеристиках рассматриваемой реализации интерфейса MPI. Полученные теоретические результаты следует подтвердить созданием параллельного алгоритма и соответствующей программы с отладкой на параллельном кластере.

Ожидаемые результаты Курсовая работа должна содержать перечисленные исследования для случаев n = 2, 3, 4, 5 с иллюстрацией результатов на параллельном кластере.

В дипломной работе (продолжение курсовой) необходимо исследовать общий случай матриц порядка n в зависимости от параметров ПВС и от параметра n. Результаты иллюстрируются программой, отлаженной на параллельном кластере.

Дальнейшее развитие результатов может содержать исследования упомянутых вопросов в различных классах матриц (в классе ленточных матриц с лентой ширины 2p + 1, в классе сеточных матриц, в классах многомерных матриц различных типов и т.п.) Рекомендации по чтению дополнительной литературы Рекомендуется первоначально читать литературу в такой последовательности 1) [1], с. 39-47, 2) [2], с. 153-159, 3) [3], с. 275-300.

[1] Форсайт Дж., Молер К. Численное решение систем линейных алгебраических уравнений. М., 1969.

[2] Корнеев В.В. Параллельные вычислительные системы. М., 1999.

[3] В.В.Воеводин, Вл.В.Воеводин. Параллельные вычисления. СПб.

2002.

Параллельное программирование с использованием интерфейса MPI в одномерной краевой задаче Введение в проблему Актуальность приближенного решения краевых задач не вызывает сомнения, поскольку эти задачи отражают фундаментальные законы природы, и к их решению сводится большое количество научных и технических проблем. С прогрессом науки и техники класс таких задач быстро расширяется, и появляется потребность быстро и достаточно точно решать такие задачи с использованием новейших компьютерных систем. Все мощные современные компьютеры снабжаются параллельными быстродействующими процессорами, так что при создании эффективных методов и алгоритмов следует принимать во внимание возможность параллельной обработки. Стандартным средством параллельного программирования является интерфейс MPI Message Passing Interface (см., например, [1], с. 153-159), реализованный на параллельных системах обычно в языках C, C ++ и F ortran в виде библиотеки процедур. Использование этого стандарта в значительной степени гарантирует переносимость и масштабируемость (т.е. независимость программы от числа используемых процессоров и других устройств);

таким образом, полученную программу можно использовать на других параллельных системах (см. [2], с. 275-300).

Постановка задачи К одномерной краевой задаче (см. [3], с. 120-126) требуется применить метод конечных элементов с кусочно-линейной аппроксимацией (см. [4], с. 38-50) и построить алгоритм для параллельной системы с использованием интерфейса MPI. Нетрудно увидеть различные возможности распараллеливания задачи (1)-(2) в зависимости от качества заданных коэффициентов k(x), a(x) и правой части f (x).

Предлагается оценить необходимый объем памяти и необходимое число тактов при определенных предположениях о параллельной системе и о характеристиках рассматриваемой реализации интерфейса MPI. Полученные теоретические результаты следует подтвердить созданием параллельного алгоритма и соответствующей программы с отладкой на параллельном кластере.

Ожидаемые результаты 1. Требуется дать детализацию метода и алгоритма решения для задачи (1)-(2) с иллюстрацией результатов на параллельном кластере.

2. Необходимо оценить нужный объем памяти и нужное число тактов при определенных предположениях о параллельной системе и о характеристиках рассматриваемой реализации процедур MPI. Полученные теоретические результаты следует сравнить с характеристиками работы программы на параллельном кластере.

Дальнейшее развитие результатов может содержать аналогичные исследования с использованием аппроксимаций более высокого порядка (вариационно-разностные методы с применением сплайнов лагранжевого и эрмитова типов, см. [5], с. 70-75) и с изучением влияния вырождения задачи на упомянутые параметры (на объем памяти и на число тактов). Аналогичные вопросы чрезвычайно интересны в двумерном и трехмерном случаях.

Рекомендации по чтению дополнительной литературы Рекомендуется первоначально читать литературу в такой последовательности 1) [3], с. 120-126, 2) [4], с. 38-50, 3) [1], с. 153-159, 4) [2], с. 275-300, 5) [5], с. 70-75.

[1] Корнеев В.В. Параллельные вычислительные системы. М., 1999.

[2] Воеводин В.В., Воеводин Вл.В.. Параллельные вычисления. СПб, 2002.

[3] Михлин С.Г. Курс математической физики. СПб, 2002.

[4] Демьянович Ю.К. Вычислительные методы для решения задач математической физики. Л., 1986.

[5] Демьянович Ю.К. Аппроксимация локальными функциями и вариационно-разностные методы. Л., 1987.

[6] Yukiya Aoyama, Jun Nakano. RS/6000 SP: Practical MPI Programming.

1999 (www.redbooks.ibm.com).

[7] Jan Forster. Parallel Programming (parallel.ru)

КУРСОВАЯ (ДИПЛОМНАЯ) РАБОТА

Распараллеливание при вычислении квадратур Введение в проблему Вычисление квадратур (отыскание определенного интеграла) очень важная практическая задача; ранее она рассматривалась со многих точек зрения. В данной работе предполагается исследование характеристик алгоритмов распараллеливания квадратурных формул для приближенного вычисления определенного интеграла. Актуальность этой задачи несомненна: с одной стороны, многие методы требуют многократно (зачастую миллионы раз) вычислять упомянутые интегралы со значительной точностью, а с другой стороны, наиболее быстрые компьютеры являются параллельными системами с большим числом (до десяти тысяч) параллельных процессоров. Каждая параллельная система снабжается средствами параллельного программирования; в большинстве случаев это интерфейс MPI Message Passing Interface (см., например, [1], с. 153-159), реализованный на параллельных системах обычно в языках C, C ++ и F ortran в виде библиотеки процедур. Использование этого стандарта в значительной степени гарантирует переносимость и масштабируемость (т.е. независимость программы от числа используемых процессоров и других устройств); таким образом, полученную программу можно использовать на других параллельных системах (см. [2], с. 275-300).

В ситуации неограниченного параллелизма (т.е. в случае, когда число процессоров системы больше количества процессоров, нужного для вычислений) некоторые аспекты распараллеливания квадратурных формул очевидны, однако из-за необходимости вычислять большое количество интегралов (см. выше) в реальной ситуации остаются нерешенными следующие задачи: как зависят число тактов и требуемый объем памяти параллельной вычислительной системы (ПВС) 1) от класса рассматриваемых подинтегральных функций, 2) от характеристик данной реализации интерфейса MPI для рассматриваемых ПВС.

Постановка задачи Приближенное вычисление интеграла проводится по квадратурной формуле вида где коэффициенты cj характеризуют применяемую квадратурную формулу (прямоугольников, трапеций, Симпсона – см. [3], с. 130-145 – или одну из согласованных со сплайнами квадратурных формул). Требуется построить алгоритм для параллельной системы с использованием интерфейса MPI. Ввиду различных возможностей распараллеливания формулы (2) в зависимости от класса заданных функций f (x) предлагается ограничиться классами функций C i [a, b], i = 0, 1, 2, 3, 4, и классами с предписанным порядком роста производных:

где константы di и Di от x (a, b] и от f не зависят, q то или иное фиксированное вещественное число, q R, а i = 0, 1, 2, 3, 4.

В перечисленных условиях нужно оценить необходимый объем памяти и необходимое число тактов при определенных предположениях о параллельной системе и о характеристиках рассматриваемой реализации интерфейса MPI. Полученные теоретические результаты следует подтвердить созданием параллельного алгоритма и соответствующей программы с отладкой на параллельном кластере.

Ожидаемые результаты Курсовая работа должна содержать подробную разработку метода и алгоритма распараллеливания формул прямоугольников, трапеций, Симпсона (см. (2)) в классах C i [a, b], i = 0, 1, 2, 3, с иллюстрацией результатов на параллельном кластере.

В дипломной работе (продолжение курсовой) необходимо оценить нужный объем памяти и нужное число тактов при определенных предположениях о параллельной системе и о характеристиках рассматриваемой реализации интерфейса MPI при применении формул прямоугольi ников, трапеций, Симпсона для классов Kq при i = 0, 1, 2, 3, 4 и при некоторых значениях q. Полученные теоретические результаты следует подтвердить созданием параллельного алгоритма и соответствующей программы с отладкой на параллельном кластере.

Дальнейшее развитие результатов может содержать аналогичные исследования с использованием согласованных со сплайнами квадратурных формул и формул более высокого порядка точности (см. [4], c. 101Могут быть также детализированы характеристики рассматриваемого класса ПВС (иерархическая структура памяти ПВС, способы кэшировнания и т.п.) Рекомендации по чтению дополнительной литературы Рекомендуется первоначально читать литературу в такой последовательности 1) [3], с. 130-145, 2) [1], с. 153-159, 3) [2], с. 275-300, 4) [4], с. 101-106.

[1] Корнеев В.В. Параллельные вычислительные системы. М., 1999.

[2] Воеводин В.В., Воеводин Вл.В.. Параллельные вычисления. СПб, 2002.

[3] Мысовских И.П. Лекции по методам вычислений. СПб., 1998.

[4] Бурова И.Г., Демьянович Ю.К. Теория минимальных сплайнов.

СПб, 2000.

КУРСОВАЯ (ДИПЛОМНАЯ) РАБОТА

Метод конечных элементов на параллельной системе Введение в проблему Метод конечных элементов (МКЭ) один из основных методов численного решения краевых задач; его английское название Finite Element Method (FEM). МКЭ появился в начале прошлого века как метод расчета конструкций строительной механики; книга Зенкевича стала одной из первых книг, где дано подробное описание этого метода. Математическое обоснование МКЭ было предложено Р.Курантом в середине прошлого века. В настоящее время этот метод пользуется большой популярностью в научных кругах и среди инженерно-технических работников: имеется большое количество весьма совершенных пакетов программ расчета физических задач, в которых используется МКЭ. Однако, быстро растет количество новых краевых задач, углубляющих наше представление о прежних физических явлениях, а также возникают краевые задачи, дающие описание новых физических явлений. С другой стороны, появляется потребность в более точном и быстром решении упомянутых задач; этой потребности отвечает появление новых быстродействующих вычислительных систем. Все мощные современные вычислительные системы представляют собой компьютеры с параллельной архитектурой (см. в [1] ссылку на регулярно публикуемый в интернете список TOP500, содержащий характеристики 500 наиболее мощных вычислительных систем). Возникает задача создания методов, допускающих распараллеливание, и алгоритмов, приспособленных для эффективного выполнения на параллельной вычислительной системе (ПВС).

Таким образом распараллеливание МКЭ весьма важная теоретическая и практическая задача. Задача эта облегчается тем, что каждая параллельная система снабжается средствами параллельного программирования; в большинстве случаев это интерфейс MPI Message Passing Interface (см., например, [2], с. 153-159), реализованный на параллельных системах обычно в языках C, C ++ и F ortran в виде библиотеки процедур. Использование этого стандарта в значительной степени гарантирует переносимость и масштабируемость (т.е. независимость программы от числа используемых процессоров и других устройств);

таким образом, полученную программу можно использовать на других параллельных системах (см. [3], с. 275-300).

Постановка задачи В прямоугольной области = [a, b; c, d] с соизмеримыми сторонами, параллельными координатным осям, рассматривается краевая задача (см. [4], с. 298-308) здесь a(x, y), b(x, y), f (x, y) заданные дифференцируемые функции, а символ означает границу области.

Для решения этой задачи необходимо использовать простейший вариант МКЭ, построенный применением аппроксимации Р.Куранта на квадратной сетке (ih, jh), i = 0, 1,..., M, j = 0, 1,..., N, где M = ba def cd N = h (каждый квадрат делится на два треугольника диагональю, параллельной биссектрисе I и II квадрантов – см., например, [5], с.20-24).

В перечисленных условиях нужно оценить необходимый объем памяти и необходимое число тактов при определенных предположениях о параллельной системе и о характеристиках рассматриваемой реализации интерфейса MPI (см. [6] с. 108-116). Полученные теоретические результаты следует подтвердить созданием параллельного алгоритма и соответствующей программы с отладкой на параллельном кластере.

Ожидаемые результаты Курсовая работа должна содержать подробную разработку метода и алгоритма распараллеливания МКЭ с помощью интерфейса MPI и соответствующий вариант отлаженной программы для параллельного кластера.

В дипломной работе (продолжение курсовой) следует оценить нужный объем памяти и нужное число тактов при определенных предположениях о параллельной системе и о характеристиках рассматриваемой реализации интерфейса MPI при распараллеливании МКЭ. Полученные теоретические результаты следует проиллюстрировать на работающей программе для параллельного кластера.

Дальнейшее развитие результатов может содержать аналогичные исследования с использованием конечно-элементных аппроксимаций более высокого порядка точности (см. [7], c. 53-84). Могут быть также детализированы характеристики рассматриваемого класса ПВС (иерархическая структура памяти ПВС, способы кэшировнания и т.п.) Рекомендации по чтению дополнительной литературы Рекомендуется первоначально читать литературу в такой последовательности 2) [2], с. 153-159, 3) [3], с. 275-300, [4], с. 298-308, 4) [5], с. 19-24, 5) [6] с. 108-116, 6) [7] c. 53-84.

[1] www.parallel.ru [2] Корнеев В.В. Параллельные вычислительные системы. М., 1999.

[3] Воеводин В.В., Воеводин Вл.В.. Параллельные вычисления. СПб, 2002.

[4] Михлин С.Г. Курс математической физики. СПб, 2002.

[5] Андреев В.Б., Руховец Л.А. Проекционные методы (метод конечных элементов). Новое в науке и технике (подписная научно-популярная серия). Вып 11/1986.

[6] Yukiya Aoyama, Jun Nakano. RS/6000 SP: Practical MPI Programming.

International Technical Support Organization. IBM. See www.parallel.ru [7] Сьярле Ф. Метод конечных элементов для эллиптических задач.

М., 1980.

КУРСОВАЯ (ДИПЛОМНАЯ) РАБОТА

Распараллеливание процесса триангуляции Введение в проблему Триангуляция (подразделение на треугольники) широко применяется в методе конечных элементов (МКЭ), который часто используется для численного решения краевых задач, встречающихся на практике (см. [1] c. 53-84). При решении этих задач требуется 1)в заданную область вписать многоугольник так, чтобы его граница содержалась в достаточно малой окрестности границы упомянутой области, 2) подразделить построенный многоугольник на треугольники так, чтобы углы рассматриваемых треугольников были ограничены снизу некоторым положительным числом, не зависящим от мелкости подразделения. Обычно достаточно просто выполнить предыдущие требования при небольшом числе треугольников. Значительно сложнее построить триангулрованный вписанный в область многоугольник с большим числом треугольников (для практических целей их число достигает 106 ).

Для таких построений желательно привлекать ЭВМ. Поскольку процесс измельчения подразделения носит локальный характер, его можно проводить параллельно и эффективно использовать параллельные вычислительные системы (ПВС). Задача эта облегчается тем, что каждая параллельная система (см. сайт [2]) снабжается средствами параллельного программирования; в большинстве случаев это интерфейс MPI Message Passing Interface (см., например, [3], с. 153-159), реализованный на параллельных системах обычно в языках C, C ++ и F ortran в виде библиотеки процедур. Использование этого стандарта в значительной степени гарантирует переносимость и масштабируемость (т.е.

независимость программы от числа используемых процессоров и других устройств); таким образом, полученную программу можно использовать на других параллельных системах (см. [4], с. 275-300).

Постановка задачи Предполагается, что граница рассматриваемой области дважды непрерывно дифференцируема. Известно, что по заданному достаточно малому положительному числу h можно построить вписанный в данную область триангулированный многоугольник, граница которого целиком лежит в ch2 -окрестности границы области, а углы между ребрами, исходяцими из одной вершины, ограничены снизу положительной константой, не зависящей от h и определяемой рассматриваемой областью. Более того, внутри области (при достаточно малом h) вне некоторой C1 h-окрестности границы структура подразделения регулярна и представляет собой объединение квадратов со сторонами длины h, параллельными координатным осям; каждый из этих квадратов разбит на два треугольника диагональю, параллельной биссектрисе первого и третьего координатных углов.

Требуется разработать алгоритм измельчения заданного симплициального подразления (в двумерном случае алгоритм измельчения триангуляции) для параллельного исполнения и создать программу для параллельного кластера, реализующую упомянутое измельчение. Кроме того, нужно оценить необходимый объем памяти и необходимое число тактов при определенных предположениях о параллельной системе и о характеристиках рассматриваемой реализации интерфейса MPI (см., например, [5] с. 108-116). Полученные теоретические результаты следует подтвердить созданием параллельного алгоритма и соответствующей программы с отладкой на параллельном кластере.

Ожидаемые результаты Курсовая работа должна содержать подробную разработку метода и алгоритма распараллеливания процесса измельчения триангуляции, а также соответствующий вариант отлаженной программы для параллельного кластера.

В дипломной работе (продолжение курсовой) следует оценить нужный объем памяти и нужное число тактов при определенных предположениях о параллельной системе и о характеристиках рассматриваемой реализации интерфейса MPI при распараллеливании подразделения в случае двумерной области. Могут быть также исследованы вопросы построения соответствующих триангуляций в случае негладкой границы области. Полученные теоретические результаты следует проиллюстрировать на работающей программе для параллельного кластера.

Дальнейшее развитие результатов может содержать применение полученных алгоритмов к схеме МКЭ для некоторых краевых задач. Кроме того, интересны были бы оценки параметров реализации в зависимости от других характеристик ПВС (от иерархической структуры памяти ПВС, от способов кэшировнания и т.п.) Рекомендации по чтению дополнительной литературы Рекомендуется первоначально читать литературу в такой последовательности 1) [1], c. 53-84, 3) [3], с. 153-159, 4) [4], с. 275-300, 5) [5] с. 108-116.

[1] Сьярле Ф. Метод конечных элементов для эллиптических задач.

М., 1980.

[2] www.parallel.ru [3] Корнеев В.В. Параллельные вычислительные системы. М., 1999.

[4] Воеводин В.В., Воеводин Вл.В.. Параллельные вычисления. СПб, 2002.

[5] Yukiya Aoyama, Jun Nakano. RS/6000 SP: Practical MPI Programming.

International Technical Support Organization. IBM. See www.parallel.ru

КУРСОВАЯ (ДИПЛОМНАЯ) РАБОТА

Построение симплициального подразделения цилиндрической области с использованием параллельной системы Введение в проблему Симплициальные подразделения (разбиение на симплексы) широко используется в методе конечных элементов (МКЭ), который применяется для численного решения краевых задач, встречающихся на практике (см. [1] c. 53-84). При решении этих задач требуется 1)в заданную область вписать многогранник так, чтобы его граница содержалась в достаточно малой окрестности границы упомянутой области, 2) подразделить построенный многогранник на симплексы так, чтобы углы между их ребрами были ограничены снизу некоторым положительным числом, не зависящим от мелкости подразделения. Обычно достаточно просто выполнить предыдущие требования при небольшом числе симплексов. Значительно сложнее построить симплициально подразделенный вписанный в область многогранник с большим числом симплексов (для практических целей их число достигает 106 ). Для таких построений желательно привлекать ЭВМ. Поскольку процесс измельчения подразделения носит локальный характер, его можно проводить параллельно и эффективно использовать параллельные вычислительные системы (ПВС). Задача эта облегчается тем, что каждая параллельная система (см. сайт [2]) снабжается средствами параллельного программирования; в большинстве случаев это интерфейс MPI Message Passing Interface (см., например, [3], с. 153-159), реализованный на параллельных системах обычно в языках C, C ++ и F ortran в виде библиотеки процедур. Использование этого стандарта в значительной степени гарантирует переносимость и масштабируемость (т.е. независимость программы от числа используемых процессоров и других устройств); таким образом, полученную программу можно использовать на других параллельных системах (см. [4], с. 275-300).

Постановка задачи Рассматривается прямой цилиндр, основанием которого служит область плоскости с дважды непрерывно дифференцируемой границей.

В цилиндр вписывается симплициально подразделенный многогранник, ребра симплексов которого не превосходят заданного положительного числа h и граница которого лежит в ch2 -окрестности границы рассматриваемого цилиндра. Для упрощения алгоритма симплициальное подразделение по определенному правилу генерируется триангуляцией основания, так что основная работа алгоритма приходится на процесс измельчения этой триангуляции. Требуется изучить алгоритм и разработать его параллельную версию с использованием интерфейса MPI для реализации на ПВС. Кроме того, нужно оценить необходимый объем памяти и необходимое число тактов при определенных предположениях о параллельной системе и о характеристиках рассматриваемой реализации интерфейса MPI (см., например, [5] с. 108-116). Полученные теоретические результаты следует подтвердить созданием параллельного алгоритма и соответствующей программы с отладкой на параллельном кластере.

Ожидаемые результаты Курсовая работа должна содержать описание способа симплициального подразделения рассматриваемой трехмерной области и подробную разработку метода и алгоритма распараллеливания процесса измельчения симплициального подразделения, а также соответствующий вариант программы для параллельного кластера.

В дипломной работе (продолжение курсовой) следует оценить нужный объем памяти и нужное число тактов при определенных предположениях о параллельной системе и о характеристиках рассматриваемой реализации интерфейса MPI при распараллеливании подразделения в случае рассматриваемой трехмерной области. Полученные теоретические результаты следует проиллюстрировать на работающей программе для параллельного кластера.

Дальнейшее развитие результатов может содержать применение полученных алгоритмов к схеме МКЭ для некоторых краевых задач. Кроме того, интересны были бы оценки параметров реализации в зависимости от других характеристик ПВС (от иерархической структуры памяти ПВС, от способов кэшировнания и т.п.) Рекомендации по чтению дополнительной литературы Рекомендуется первоначально читать литературу в такой последовательности 1) [1], c. 53-84, 3) [3], с. 153-159, 4) [4], с. 275-300, 5) [5] с. 108-116.

[1] Сьярле Ф. Метод конечных элементов для эллиптических задач.

М., 1980.

[2] www.parallel.ru [3] Корнеев В.В. Параллельные вычислительные системы. М., 1999.

[4] Воеводин В.В., Воеводин Вл.В.. Параллельные вычисления. СПб, 2002.

[5] Yukiya Aoyama, Jun Nakano. RS/6000 SP: Practical MPI Programming.

International Technical Support Organization. IBM. See www.parallel.ru

КУРСОВАЯ (ДИПЛОМНАЯ) РАБОТА

Распараллеливание МКЭ для одной нестационарной задачи Введение в проблему Метод конечных элементов (МКЭ) один из основных методов численного решения краевых задач; его английское название Finite Element Method (FEM). МКЭ появился в начале прошлого века как метод расчета конструкций строительной механики; книга Зенкевича стала одной из первых книг, где дано подробное описание этого метода. Математическое обоснование МКЭ было предложено Р.Курантом в середине прошлого века. В настоящее время этот метод пользуется большой популярностью в научных кругах и среди инженерно-технических работников: имеется большое количество весьма совершенных пакетов программ расчета физических задач, в которых используется МКЭ. Однако, быстро растет количество новых краевых задач, углубляющих наше представление о прежних физических явлениях, а также возникают краевые задачи, дающие описание новых физических явлений. С другой стороны, появляется потребность в более точном и быстром решении упомянутых задач; этой потребности отвечает появление новых быстродействующих вычислительных систем. Все мощные современные вычислительные системы представляют собой компьютеры с параллельной архитектурой (см. в [1] ссылку на регулярно публикуемый в интернете список TOP500, содержащий характеристики 500 наиболее мощных вычислительных систем). Возникает задача создания методов, допускающих распараллеливание, и алгоритмов, приспособленных для эффективного выполнения на параллельной вычислительной системе (ПВС).

Таким образом распараллеливание МКЭ весьма важная теоретическая и практическая задача. Задача эта облегчается тем, что каждая параллельная система снабжается средствами параллельного программирования; в большинстве случаев это интерфейс MPI Message Passing Interface (см., например, [2], с. 153-159), реализованный на параллельных системах обычно в языках C, C ++ и F ortran в виде библиотеки процедур. Использование этого стандарта в значительной степени гарантирует переносимость и масштабируемость (т.е. независимость программы от числа используемых процессоров и других устройств);

таким образом, полученную программу можно использовать на других параллельных системах (см. [3], с. 275-300).

Постановка задачи На конечном временнм интервале (0, T ] в прямоугольной области = [a, b; c, d] с соизмеримыми сторонами, параллельными координатным осям, рассматривается начально-краевая задача здесь a(x, y), b(x, y), f (x, y), u0 (x, y) заданные дифференцируемые функции, а символ означает границу области (более общие задачи см. в [4], с. 422-429).

Для решения этой задачи необходимо по пространственной переменной использовать простейший вариант МКЭ, построенный применением аппроксимации Р.Куранта на квадратной сетке (ih, jh), i = 0, 1,..., M, j = 0, 1,..., N, где M = ba N = cd (каждый квадрат делится на два треdef def угольника диагональю, параллельной биссектрисе I и II квадрантов – см., например, [5], с.20-24), а по временнй переменной рассмотреть апо проксимацию с весами (см., например, [6], c. 344-349).

В перечисленных условиях нужно оценить необходимый объем памяти и необходимое число тактов при определенных предположениях о параллельной системе и о характеристиках рассматриваемой реализации интерфейса MPI (см. [7] с. 108-116). Полученные теоретические результаты следует подтвердить созданием параллельного алгоритма и соответствующей программы с отладкой на параллельном кластере.

Ожидаемые результаты Курсовая работа должна содержать подробную разработку метода и алгоритма распараллеливания МКЭ с помощью интерфейса MPI и соответствующий вариант отлаженной программы для параллельного кластера.

В дипломной работе (продолжение курсовой) следует оценить нужный объем памяти и нужное число тактов при определенных предположениях о параллельной системе и о характеристиках рассматриваемой реализации интерфейса MPI при распараллеливании МКЭ. Полученные теоретические результаты следует проиллюстрировать на работающей программе для параллельного кластера.

Дальнейшее развитие результатов может содержать аналогичные исследования с использованием конечно-элементных аппроксимаций более высокого порядка точности (см. [8], c. 53-84). Могут быть также детализированы характеристики рассматриваемого класса ПВС (иерархическая структура памяти ПВС, способы кэшировнания и т.п.) Рекомендации по чтению дополнительной литературы Рекомендуется первоначально читать литературу в такой последовательности 2) [2], с. 153-159, 3) [3], с. 275-300, [4], с. 422-429, 4) [5], с. 19-24, 5) [7], с. 108-116, 6) [8], c. 53-84, 7) [6], c. 344-349.

[1] www.parallel.ru [2] Корнеев В.В. Параллельные вычислительные системы. М., 1999.

[3] Воеводин В.В., Воеводин Вл.В.. Параллельные вычисления. СПб, 2002.

[4] Михлин С.Г. Курс математической физики. СПб, 2002.

[5] Андреев В.Б., Руховец Л.А. Проекционные методы (метод конечных элементов). Новое в науке и технике (подписная научно-популярная серия). Вып 11/1986.

[6] Демьянович В.К., Демьянович Ю.К. О скорости сходимости проекционных методов для параболических уравнений// Журн. выч. мат.

и мат. физ., 1968. Т.8, № 2. С. 344-362.

[7] Yukiya Aoyama, Jun Nakano. RS/6000 SP: Practical MPI Programming.

International Technical Support Organization. IBM. See www.parallel.ru [8] Сьярле Ф. Метод конечных элементов для эллиптических задач.

М., 1980.

КУРСОВАЯ (ДИПЛОМНАЯ) РАБОТА

Распараллеливание вычислений тригонометрических функций Введение в проблему При создании вычислительных систем (ВС) на определенном этапе возникает вопрос об их оснащении математическим обеспечением, которое позволяло бы в дальнейшем эффективно использовать ВС на практике. Математическое обеспечение может быть приданным (программное обеспечение) и встроенным (аппаратные средства). Одной из частей этой проблемы является проблема реализации вычислений элементарных функций. Хотя эта проблема имеет давнюю историю, но в связи с постоянным совершенствованием вычислительных средств она является теперь в новом свете. Дело в том, что все мощные современные вычислительные системы представляют собой компьютеры с параллельной архитектурой (см. в [1] ссылку на регулярно публикуемый в интернете список TOP500, содержащий характеристики 500 наиболее мощных вычислительных систем). Возникает задача создания методов, допускающих распараллеливание, и алгоритмов, приспособленных для эффективного выполнения на параллельной вычислительной системе (ПВС). Во многих случаях эта задача облегчается тем, что каждая параллельная система снабжается средствами параллельного программирования; в большинстве случаев это интерфейс MPI Message Passing Interface (см., например, [2], с. 153-159), реализованный на параллельных системах обычно в языках C, C ++ и F ortran в виде библиотеки процедур. Использование этого стандарта в значительной степени гарантирует переносимость и масштабируемость (т.е. независимость программы от числа используемых процессоров и других устройств);

таким образом, полученную программу можно использовать на других параллельных системах (см. [3], с. 275-300).

Однако, для рассматриваемого здесь вопроса о распараллеливании тригонометрических функций стандарт MPI может быть интересен только в ситуации создания программных средств вычисления; для эффективности вычисления тригонометрических функций обычно реализуются аппаратно.

Существует много методов аппаратной реализации вычисления элементарных функций (см. [4], с. 6-32). При этом следует обратить внимание на 1) определенность алгоритма вычисления, 2) сходимость алгоритма, 3) устойчивость алгоритма относительно ошибок округлния, 4) разрядность сетки рассматриваемой вычислительной системы, 5) число операций, необходимых для достижения заданной точности.

В случае использования ПВС дополнительно возникают вопросы:

a) возможно ли распараллелить вычислительный процесс, b) каковы ответы на предыдущие пункты 1) - 5) при различных вариантах распараллеливания (эти ответы могут существенно различаться!), c) каковы характеристики вариантов распараллеливания с точки зрения используемой ПВС (объем необходимой памяти, число тактов, загруженность системы и т.п.) d) какие задачи предполагается решать на ПВС (каков класс задач), e) как определить "наилучший" из вариантов (или что считать "наилучшим" вариантом).

Постановка задачи Требуется разработать алгоритмы вычисления тригонометрических функций для ПВС с использованием следующих подходов:

– разложение в ряд Тейлора, – аппроксимация с помощью полинома, – аппроксимация с помощью сплайна, – аппроксимация цепной дробью, – аппроксимация с помощью таблицы, – аппроксимация с использованием итерационных методов.

При этом требуется сравнить эти подходы между собой руководствуясь пунктами 1)-5) и a)-e).

Ожидаемые результаты Курсовая работа должна содержать подробную разработку метода и алгоритма распараллеливания вычисления тригонометрических функций, перечисленных выше, а также содержать моделирование этих вычислений с помощью интерфейса MPI для параллельного кластера.

В дипломной работе (продолжение курсовой) следует оценить нужный объем памяти и нужное число тактов при определенных предположениях о параллельной системе, соответствующей AltiVec Technology /Motorola/ (см. сайт [5]). Полученные теоретические результаты следует проиллюстрировать на работающей программе для параллельного кластера.

Дальнейшее развитие результатов может содержать создание программы моделирования AltiVec Technology при параллельном вычислении перечисленных функций. Могут быть также детализированы характеристики рассматриваемого класса ПВС (иерархическая структура памяти ПВС, способы кэшировнания и т.п.) Рекомендации по чтению дополнительной литературы Рекомендуется первоначально читать литературу в такой последовательности 2) [2], с. 153-159, 3) [3], с. 275-300, 4) [4], с. 6-32, [1] www.parallel.ru [2] Корнеев В.В. Параллельные вычислительные системы. М., 1999.

[3] Воеводин В.В., Воеводин Вл.В.. Параллельные вычисления. СПб, 2002.

[4] Байков В.Д., Смолов В.Б. Аппаратурная реализация элементарных функций в ЦВМ. Л., 1975.

[5] www.motorola.com

КУРСОВАЯ (ДИПЛОМНАЯ) РАБОТА

Распараллеливание вычислений экспоненциальной Введение в проблему При создании вычислительных систем (ВС) на определенном этапе возникает вопрос об их оснащении математическим обеспечением, которое позволяло бы в дальнейшем эффективно использовать ВС на практике. Математическое обеспечение может быть прданным (прои граммное обеспечение) и встроенным (аппаратные средства). Одной из частей этой проблемы является проблема реализации вычислений элементарных функций. Хотя эта проблема имеет давнюю историю, но в связи с постоянным совершенствованием вычислительных средств она является теперь в новом свете. Дело в том, что все мощные современные вычислительные системы представляют собой компьютеры с параллельной архитектурой (см. в [1] ссылку на регулярно публикуемый в интернете список TOP500, содержащий характеристики 500 наиболее мощных вычислительных систем). Возникает задача создания методов, допускающих распараллеливание, и алгоритмов, приспособленных для эффективного выполнения на параллельной вычислительной системе (ПВС). Во многих случаях эта задача облегчается тем, что каждая параллельная система снабжается средствами параллельного программирования; в большинстве случаев это интерфейс MPI Message Passing Interface (см., например, [2], с. 153-159), реализованный на параллельных системах обычно в языках C, C ++ и F ortran в виде библиотеки процедур. Использование этого стандарта в значительной степени гарантирует переносимость и масштабируемость (т.е. независимость программы от числа используемых процессоров и других устройств);

таким образом, полученную программу можно использовать на других параллельных системах (см. [3], с. 275-300).

Однако, для рассматриваемого здесь вопроса о распараллеливании экспоненциальной и логарифмической функций стандарт MPI может быть интересен только в ситуации создания программных средств вычисления; для эффективности вычисления экспоненциальной и логарифмической функций обычно реализуются аппаратно.

Существует много методов аппаратной реализации вычисления элементарных функций (см. [4], с. 6-32). При этом следует обратить внимание на 1) определенность алгоритма вычисления, 2) сходимость алгоритма, 3) устойчивость алгоритма относительно ошибок округлния, 4) разрядность сетки рассматриваемой вычислительной системы, 5) число операций, необходимых для достижения заданной точности.

В случае использования ПВС дополнительно возникают вопросы:

a) возможно ли распараллелить вычислительный процесс, b) каковы ответы на предыдущие пункты 1) - 5) при различных вариантах распараллеливания (эти ответы могут существенно различаться!), c) каковы характеристики вариантов распараллеливания с точки зрения используемой ПВС (объем необходимой памяти, число тактов, загруженность системы и т.п.) d) какие задачи предполагается решать на ПВС (каков класс задач), e) как определить "наилучший" из вариантов (или что считать "наилучшим" вариантом).

Постановка задачи Требуется разработать алгоритмы вычисления экспоненциальной и логарифмической функций exp(x), loga (x), a > 0, a = 1, для ПВС с использованием следующих подходов:

– разложение в ряд Тейлора, – аппроксимация с помощью полинома, – аппроксимация с помощью сплайна, – аппроксимация цепной дробью, – аппроксимация с помощью таблицы, – аппроксимация с использованием итерационных методов.

При этом требуется сравнить эти подходы между собой руководствуясь пунктами 1)-5) и a)-e).

Ожидаемые результаты Курсовая работа должна содержать подробную разработку метода и алгоритма распараллеливания вычисления экспоненциальной и логарифмической функций, а также содержать моделирование этих вычислений с помощью интерфейса MPI для параллельного кластера.

В дипломной работе (продолжение курсовой) следует оценить нужный объем памяти и нужное число тактов при определенных предположениях о параллельной системе, соответствующей AltiVec Technology /Motorola/ (см. сайт [5]). Полученные теоретические результаты следует проиллюстрировать на работающей программе для параллельного кластера.

Дальнейшее развитие результатов может содержать создание программы моделирования AltiVec Technology при параллельном вычислении перечисленных функций. Могут быть также детализированы характеристики рассматриваемого класса ПВС (иерархическая структура памяти ПВС, способы кэшировнания и т.п.) Рекомендации по чтению дополнительной литературы Рекомендуется первоначально читать литературу в такой последовательности 2) [2], с. 153-159, 3) [3], с. 275-300, 4) [4], с. 6-32, [1] www.parallel.ru [2] Корнеев В.В. Параллельные вычислительные системы. М., 1999.

[3] Воеводин В.В., Воеводин Вл.В.. Параллельные вычисления. СПб, 2002.

[4] Байков В.Д., Смолов В.Б. Аппаратурная реализация элементарных функций в ЦВМ. Л., 1975.

[5] www.motorola.com

КУРСОВАЯ (ДИПЛОМНАЯ) РАБОТА

обратных тригонометрических функций Введение в проблему При создании вычислительных систем (ВС) на определенном этапе возникает вопрос об их оснащении математическим обеспечением, которое позволяло бы в дальнейшем эффективно использовать ВС на практике. Математическое обеспечение может быть прданным (прои граммное обеспечение) и встроенным (аппаратные средства). Одной из частей этой проблемы является проблема реализации вычислений элементарных функций. Хотя эта проблема имеет давнюю историю, но в связи с постоянным совершенствованием вычислительных средств она является теперь в новом свете. Дело в том, что все мощные современные вычислительные системы представляют собой компьютеры с параллельной архитектурой (см. в [1] ссылку на регулярно публикуемый в интернете список TOP500, содержащий характеристики 500 наиболее мощных вычислительных систем). Возникает задача создания методов, допускающих распараллеливание, и алгоритмов, приспособленных для эффективного выполнения на параллельной вычислительной системе (ПВС). Во многих случаях эта задача облегчается тем, что каждая параллельная система снабжается средствами параллельного программирования; в большинстве случаев это интерфейс MPI Message Passing Interface (см., например, [2], с. 153-159), реализованный на параллельных системах обычно в языках C, C ++ и F ortran в виде библиотеки процедур. Использование этого стандарта в значительной степени гарантирует переносимость и масштабируемость (т.е. независимость программы от числа используемых процессоров и других устройств);

таким образом, полученную программу можно использовать на других параллельных системах (см. [3], с. 275-300).

Однако, для рассматриваемого здесь вопроса о распараллеливании обратных тригонометрических функций стандарт MPI может быть интересен только в ситуации создания программных средств вычисления;

для эффективности вычисление обратных тригонометрических функций обычно реализуется аппаратно.

Существует много методов аппаратной реализации вычисления элементарных функций (см. [4], с. 6-32). При этом следует обратить внимание на 1) определенность алгоритма вычисления, 2) сходимость алгоритма, 3) устойчивость алгоритма относительно ошибок округлния, 4) разрядность сетки рассматриваемой вычислительной системы, 5) число операций, необходимых для достижения заданной точности.

В случае использования ПВС дополнительно возникают вопросы:

a) возможно ли распараллелить вычислительный процесс, b) каковы ответы на предыдущие пункты 1) - 5) при различных вариантах распараллеливания (эти ответы могут существенно различаться!), c) каковы характеристики вариантов распараллеливания с точки зрения используемой ПВС (объем необходимой памяти, число тактов, загруженность системы и т.п.) d) какие задачи предполагается решать на ПВС (каков класс задач), e) как определить "наилучший" из вариантов (или что считать "наилучшим" вариантом).

Постановка задачи Требуется разработать алгоритмы вычисления обратных тригонометрических функций arcsin(x), arccos(x), arctg(x), arcctg(x) для ПВС с использованием следующих подходов:

– разложение в ряд Тейлора, – аппроксимация с помощью полинома, – аппроксимация с помощью сплайна, – аппроксимация цепной дробью, – аппроксимация с помощью таблицы, – аппроксимация с использованием итерационных методов.

При этом требуется сравнить эти подходы между собой руководствуясь пунктами 1)-5) и a)-e).

Ожидаемые результаты Курсовая работа должна содержать подробную разработку метода и алгоритма распараллеливания вычисления экспоненциальной и логарифмической функций, а также содержать моделирование этих вычислений с помощью интерфейса MPI для параллельного кластера.

В дипломной работе (продолжение курсовой) следует оценить нужный объем памяти и нужное число тактов при определенных предположениях о параллельной системе, соответствующей AltiVec Technology /Motorola/ (см. сайт [5]). Полученные теоретические результаты следует проиллюстрировать на работающей программе для параллельного кластера.

Дальнейшее развитие результатов может содержать создание программы моделирования AltiVec Technology при параллельном вычислении перечисленных функций. Могут быть также детализированы характеристики рассматриваемого класса ПВС (иерархическая структура памяти ПВС, способы кэшировнания и т.п.) Рекомендации по чтению дополнительной литературы Рекомендуется первоначально читать литературу в такой последовательности 2) [2], с. 153-159, 3) [3], с. 275-300, 4) [4], с. 6-32, [1] www.parallel.ru [2] Корнеев В.В. Параллельные вычислительные системы. М., 1999.

[3] Воеводин В.В., Воеводин Вл.В.. Параллельные вычисления. СПб, 2002.

[4] Байков В.Д., Смолов В.Б. Аппаратурная реализация элементарных функций в ЦВМ. Л., 1975.

[5] www.motorola.com

КУРСОВАЯ (ДИПЛОМНАЯ) РАБОТА

обратных гиперболических функций Введение в проблему При создании вычислительных систем (ВС) на определенном этапе возникает вопрос об их оснащении математическим обеспечением, которое позволяло бы в дальнейшем эффективно использовать ВС на практике. Математическое обеспечение может быть прданным (прои граммное обеспечение) и встроенным (аппаратные средства). Одной из частей этой проблемы является проблема реализации вычислений элементарных функций. Хотя эта проблема имеет давнюю историю, но в связи с постоянным совершенствованием вычислительных средств она является теперь в новом свете. Дело в том, что все мощные современные вычислительные системы представляют собой компьютеры с параллельной архитектурой (см. в [1] ссылку на регулярно публикуемый в интернете список TOP500, содержащий характеристики 500 наиболее мощных вычислительных систем). Возникает задача создания методов, допускающих распараллеливание, и алгоритмов, приспособленных для эффективного выполнения на параллельной вычислительной системе (ПВС). Во многих случаях эта задача облегчается тем, что каждая параллельная система снабжается средствами параллельного программирования; в большинстве случаев это интерфейс MPI Message Passing Interface (см., например, [2], с. 153-159), реализованный на параллельных системах обычно в языках C, C ++ и F ortran в виде библиотеки процедур. Использование этого стандарта в значительной степени гарантирует переносимость и масштабируемость (т.е. независимость программы от числа используемых процессоров и других устройств);

таким образом, полученную программу можно использовать на других параллельных системах (см. [3], с. 275-300).

Однако, для рассматриваемого здесь вопроса о распараллеливании обратных гиперболических функций стандарт MPI может быть интересен только в ситуации создания программных средств вычисления;

для эффективности вычисление этих функций обычно реализуется аппаратно.

Существует много методов аппаратной реализации вычисления элементарных функций (см. [4], с. 6-32). При этом следует обратить внимание на 1) определенность алгоритма вычисления, 2) сходимость алгоритма, 3) устойчивость алгоритма относительно ошибок округлния, 4) разрядность сетки рассматриваемой вычислительной системы, 5) число операций, необходимых для достижения заданной точности.

В случае использования ПВС дополнительно возникают вопросы:

a) возможно ли распараллелить вычислительный процесс, b) каковы ответы на предыдущие пункты 1) - 5) при различных вариантах распараллеливания (эти ответы могут существенно различаться!), c) каковы характеристики вариантов распараллеливания с точки зрения используемой ПВС (объем необходимой памяти, число тактов, загруженность системы и т.п.) d) какие задачи предполагается решать на ПВС (каков класс задач), e) как определить "наилучший" из вариантов (или что считать "наилучшим" вариантом).

Постановка задачи Требуется разработать алгоритмы вычисления обратных гиперболических функций Arsh(x), Arch(x), Arth(x), Arcth(x) (см. [5], c. 44) для ПВС с использованием следующих подходов:

– разложение в ряд Тейлора, – аппроксимация с помощью полинома, – аппроксимация с помощью сплайна, – аппроксимация цепной дробью, – аппроксимация с помощью таблицы, – аппроксимация с использованием итерационных методов.

При этом требуется сравнить эти подходы между собой руководствуясь пунктами 1)-5) и a)-e).

Ожидаемые результаты Курсовая работа должна содержать подробную разработку метода и алгоритма распараллеливания вычисления экспоненциальной и логарифмической функций, а также содержать моделирование этих вычислений с помощью интерфейса MPI для параллельного кластера.

В дипломной работе (продолжение курсовой) следует оценить нужный объем памяти и нужное число тактов при определенных предположениях о параллельной системе, соответствующей AltiVec Technology /Motorola/ (см. сайт [6]). Полученные теоретические результаты следует проиллюстрировать на работающей программе для параллельного кластера.

Дальнейшее развитие результатов может содержать создание программы моделирования AltiVec Technology при параллельном вычислении перечисленных функций. Могут быть также детализированы характеристики рассматриваемого класса ПВС (иерархическая структура памяти ПВС, способы кэшировнания и т.п.) Рекомендации по чтению дополнительной литературы Рекомендуется первоначально читать литературу в такой последовательности 2) [2], с. 153-159, 3) [3], с. 275-300, 4) [4], с. 6-32, 5) [5] с. 44, [1] www.parallel.ru [2] Корнеев В.В. Параллельные вычислительные системы. М., 1999.

[3] Воеводин В.В., Воеводин Вл.В.. Параллельные вычисления. СПб, 2002.

[4] Байков В.Д., Смолов В.Б. Аппаратурная реализация элементарных функций в ЦВМ. Л., 1975.

[5] Янке Е., Эмде Ф., Леш Ф. Специальные функции (формулы, графики, таблицы). М., 1968.

[6] www.motorola.com

КУРСОВАЯ (ДИПЛОМНАЯ) РАБОТА

Введение в проблему Дискретное преобразование Фурье (ДПФ) широко применяется при анализе дискретных сигналов для выделения из них основной информационной части. Подобная обработка необходима для процессов сжатия и восстановления информации при передаче аудио- и видео-сигналов на большие расстояния, а также при анализе томографической информации и т.п. Ввиду чрезвычайно больших объемов подобной информации были разработаны быстрые методы ее обработки: быстрое преобразование Фурье (БПФ Кули-Тьюки), алгоритм Винограда и др. Основная идея этих методов в однократной обработке часто встречающихся в преобразовании одинаковых выражений; эта идея реализуется соответствующей группировкой выражений и правильной последовательностью их вычисления. Многие из этих методов допускают эффективное распараллеливание, а следовательно, эффективную реализацию на параллельных вычислительных системах (ПВС). Во многих случаях эта задача облегчается тем, что каждая параллельная система снабжается средствами параллельного программирования; в большинстве случаев это интерфейс MPI Message Passing Interface (см., например, [2], с. 153-159), реализованный на параллельных системах обычно в языках C, C ++ и F ortran в виде библиотеки процедур. Использование этого стандарта в значительной степени гарантирует переносимость и масштабируемость (т.е. независимость программы от числа используемых процессоров и других устройств); таким образом, полученную программу можно использовать на других параллельных системах (см. [3], с.

275-300).

Постановка задачи Требуется изучить алгоритмы вычисления БПФ Кули-Тьюки (см. [4], с. 128-141) и разработать параллельный вариант этих алгоритмов для реализации на ПВС.

Ожидаемые результаты Курсовая работа должна содержать подробную разработку метода и алгоритма распараллеливания БПФ Кули-Тьюки, также программу для параллельного кластера.

В дипломной работе (продолжение курсовой) следует оценить нужный для распараллеливания БПФ Кули-Тьюки объем памяти и нужное число тактов при определенных предположениях о параллельной системе. Полученные теоретические результаты должны быть проиллюстрированы на работающей программе для параллельного кластера.

Дальнейшее развитие результатов может относится к распараллеливанию вычисления свертки с помощью преобразования Фурье, а также алгоритма Винограда для быстрого вычисления свертки малой длины (см. [4], с. 147-167). Могут быть также детализированы характеристики рассматриваемого класса ПВС (иерархическая структура памяти ПВС, способы кэшировнания и т.п.) Рекомендации по чтению дополнительной литературы Рекомендуется первоначально читать литературу в такой последовательности 2) [2], с. 153-159, 3) [3], с. 275-300, 4) [4], с. 128- 5) [5] с. 17- [1] www.parallel.ru [2] Корнеев В.В. Параллельные вычислительные системы. М., 1999.

[3] Воеводин В.В., Воеводин Вл.В.. Параллельные вычисления. СПб, 2002.

[4] Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов.

М., 1989.

[5] Демьянович Ю.К. Лекции по компьютерной алгебре. Системы аналитических вычислений. СПб, 1999.

[6] Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычислительных алгоритмов. М., 1979.

КУРСОВАЯ (ДИПЛОМНАЯ) РАБОТА

минимальных полиномиальных сплайнов Введение в проблему Минимальные полиномиальные сплайны являются достаточно простым и надежным аппаратом приближения. Они обладают свойством локальности (значения аппроксимируемой функции в точках, удаленных от рассматриваемой, не влияют на аппроксимацию в рассматриваемой точке), устойчивостью (малые изменения данных влекут малое изменение аппроксимации), при заданной точности они обладают минимальной кратностью пересечения носителей базисных функций (что ведет к минимальной ширине ленты у соответствующей матрицы Грама), небольшой вычислительной сложностью (например, требуется небольшое число арифметических действий для вычисления аппроксимации в заданной точке), вычислительная сложность не зависит от шага рассматриваемой сетки (шаг обычно стремится к нулю), а зависит лишь от степени сплайна (она обычно считается фиксированной). Эти и другие свойства привлекают исследователей и практиков, так что сплайны находят широчайшие применения практически во всех областях науки и техники. Поскольку вычислительная техника быстро развивается, то необходимо постоянно менять вычислительные алгоритмы и программы с тем, чтобы в новых условиях аппарат сплайнов сохранял свою эффективность.

В данной работе предполагается исследование характеристик алгоритмов распараллеливания сплайновых аппроксимаций при различных предположениях относительно вычислительного устройства. Наиболее быстрыми компьютерами сейчас являются параллельные системы с большим числом (до десяти тысяч) параллельных процессоров. Каждая параллельная система снабжается средствами параллельного программирования; в большинстве случаев это интерфейс MPI Message Passing Interface (см., например, [1], с. 153-159), реализованный на параллельных системах обычно в языках C, C ++ и F ortran в виде библиотеки процедур. Использование этого стандарта в значительной степени гарантирует переносимость и масштабируемость (т.е. независимость программы от числа используемых процессоров и других устройств); таким образом, полученную программу можно использовать на других параллельных системах (см. [2], с. 275-300).

В ситуации неограниченного параллелизма (т.е. в случае, когда число процессоров системы больше количества процессоров, нужного для вычислений) некоторые аспекты распараллеливания вычисления сплайнов очевидны, однако из-за необходимости вычислять большое количество сплайнов (см. выше) в реальной ситуации остаются нерешенными следующие задачи: как зависят число тактов и требуемый объем памяти параллельной вычислительной системы (ПВС) 1) от класса аппроксимируемых функций, 2) от класса рассматриваемых сплайновых аппроксимаций, 3) от характеристик данной реализации интерфейса MPI для рассматриваемых ПВС.

Постановка задачи Пространство минимальных сплайнов степени m 1 на равномерной сетке шага h > 0 получается (см. [3], с. 251-270), как линейная оболочка функций (µ) ( h j), где j пробегает все целые числа, а функция (µ) (t) отлична от нуля разве лишь на отрезке [0, m + 1], а при каждом фиксированном t (k, k + 1), k = 0, 1,..., m, она определяется из системы линейных алгебраических уравнений здесь m заданное натуральное число, а µ = (µ0, µ1,..., µm ) заданm ный вектор, у которого µ0 = 1. Функция (µ) (t) называется образующим минимальным сплайном, а линейная комбинация с произвольными вещественными коэффициентами vj называется µ-сплайном степени m (нетрудно проверить, что при фиксированном x сумма (2) содержит разве лишь m+1 ненулевых слагаемых).

При m = 1 система (1) состоит из двух уравнений с двумя неизвестными (µ) (t k + 1) и (µ) (t k) (напомним, что t фиксированное число из промежутка (k, k + 1)). Легко проверить, что при решении такой системы зависимость от k в конечном счете исчезает; в результате приходим к сплайну Среди таких сплайнов существует единственный непрерывный сплайн:

это B-сплайн первой степени, получающийся при µ = µ, µ = (1, 1).

При m = 2 система (1) содержит три уравнения с тремя неизвестными (µ) (t k + 2), (µ) (t k + 1) и (µ) (t k), откуда находим квадратичный сплайн среди которых единственным сплайном класса C 1 является квадратичB def ный B-сплайн, получающийся при µ = µ = (1, 3/2, 5/2).

Требуется построить алгоритм вычисления образующего минимальm ного сплайна (µ) (t) и линейной комбинации (2) при фиксированном t для параллельной системы с использованием интерфейса MPI и оценить необходимый объем памяти и необходимое число тактов при определенных предположениях о параллельной системе и о характеристиках рассматриваемой реализации интерфейса MPI в зависимости от значения векторного параметра µ (например, наличие нулевых компонент у этого вектора уменьшает число арфметических действий). Полученные теоретические результаты следует подтвердить созданием параллельного алгоритма и соответствующей программы с отладкой на параллельном кластере.

Ожидаемые результаты Курсовая работа должна содержать подробную разработку метода и алгоритма распараллеливания формул (3), (4), а также формул (2) (при m = 1, 2) для параллельной системы с использованием интерфейса MPI и оценить необходимый объем памяти и необходимое число тактов при определенных предположениях о параллельной системе и о характеристиках рассматриваемой реализации интерфейса MPI в зависимости от значения векторного параметра µ с иллюстрацией результатов на параллельном кластере.

В дипломной работе (продолжение курсовой) необходимо обобщить полученные в курсовой работе результаты на случай произвольного m (см. формулы (1) и (2)), т.е. дать подробную разработку метода и алгоритма распараллеливания вычисления упомянутого сплайна для параллельной системы с использованием интерфейса MPI и оценить необходимый объем памяти и необходимое число тактов при определенных предположениях о параллельной системе и о характеристиках рассматриваемой реализации интерфейса MPI в зависимости от значения векторного параметра µ. Полученные теоретические результаты следует подтвердить созданием параллельного алгоритма и соответствующей программы с отладкой на параллельном кластере.

Дальнейшее развитие результатов может содержать аналогичные исследования в отношении сплайнов на гладких одномерных многообразиях (т.е. на кривых линиях, в частности, на окружности; см. [4], c.

17-21). Могут быть также детализированы характеристики рассматриваемого класса ПВС (иерархическая структура памяти ПВС, способы кэшировнания и т.п.) Рекомендации по чтению дополнительной литературы Рекомендуется первоначально читать литературу в такой последовательности 1) [3], с. 251-270, 2) [1], с. 153-159, 3) [2], с. 275-300, 4) [4], с. 17-21.

[1] Корнеев В.В. Параллельные вычислительные системы. М., 1999.

[2] Воеводин В.В., Воеводин Вл.В.. Параллельные вычисления. СПб, 2002.

[3] Бурова И.Г., Демьянович Ю.К. Теория минимальных сплайнов.

СПб, 2000.

[4] Демьянович Ю.К. Аппроксимация на многообразии и минимальные сплайны. СПб, 1994.

КУРСОВАЯ (ДИПЛОМНАЯ) РАБОТА

Введение в проблему Метод конечных элементов (МКЭ) один из основных методов численного решения краевых задач (см. по этому поводу введение к теме №5); его английское название Finite Element Method (FEM). Этот метод относится к проекционным методам (см. [1], с. 199-203), построение приближенного уравнения в которых условно делится на два этапа:

1) выбор пространства проектирования (этим этапом определяется качество искомого приближения), 2) построение операции проектирования (здесь определяется уравнение, из которого будет определяться приближенное решение).

Метод конечных элементов выделяется из проекционных методов специальным выбором пространства проектирования и особым способом построения операции проектирования. Пространства для этого метода первоначально выбирали так, чтобы отыскиваемые в МКЭ параметры имели определенный механический смысл, теперь же часто при выборе пространств руководствуются соображениями вычислительного плана (оптимальностью аппроксимации, устойчивостью счета, сокращением числа арифметических действий и т.п.). Однако, во всех случаях рассматривают пространства локальных функций (линейную оболочку функций с малым носителем). Среди них особенно часто используют пространства Куранта, Зламала, Аргириса и др. (как на плоскости, так и в пространстве, см. [2], 53-83). Поскольку перечисленные пространства обладают интерполяционными и аппроксимационными свойствами, то их можно использовать и для построения аппроксимаций функций, известных лишь в некоторой системе узлов на плоскости (или в пространстве). Вычисление таких аппроксимаций при большом количестве точек требует специальных приемов, ускоряющих вычисление, а также достаточно мощных вычислительных систем. Все мощные современные вычислительные системы представляют собой компьютеры с параллельной архитектурой (см. в [3] ссылку на регулярно публикуемый в интернете список TOP500, содержащий характеристики наиболее мощных вычислительных систем). Возникает задача создания методов, допускающих распараллеливание, и алгоритмов, приспособленных для эффективного выполнения на параллельной вычислительной системе (ПВС). Таким образом распараллеливание МКЭ весьма важная теоретическая и практическая задача. Задача эта облегчается тем, что каждая параллельная система снабжается средствами параллельного программирования; в большинстве случаев это интерфейс MPI Message Passing Interface (см., например, [4], с. 153-159), реализованный на параллельных системах обычно в языках C, C ++ и F ortran в виде библиотеки процедур. Использование этого стандарта в значительной степени гарантирует переносимость и масштабируемость (т.е.

независимость программы от числа используемых процессоров и других устройств); таким образом, полученную программу можно использовать на других параллельных системах (см. [5], с. 275-300).

В данной работе предполагается исследование характеристик алгоритмов распараллеливания МКЭ-аппроксимаций при различных предположениях относительно вычислительного устройства.

В ситуации неограниченного параллелизма (т.е. в случае, когда число процессоров системы больше количества процессоров, нужного для вычислений) некоторые аспекты распараллеливания вычисления МКЭаппроксимаций очевидны, однако в реальной ситуации остаются нерешенными следующие задачи: как зависят число тактов и требуемый объем памяти ПВС 1) от класса аппроксимируемых функций, 2) от класса рассматриваемых МКЭ-аппроксимаций, 3) от характеристик данной реализации интерфейса MPI для рассматриваемых ПВС.

Постановка задачи В данной работе предлагается разработать методику и алгоритм вычисления аппроксимаций Куранта и Зламала на параллельной системе с использованием интерфейса MPI и оценить необходимый объем памяти и необходимое число тактов при определенных предположениях о параллельной системе и о характеристиках рассматриваемой реализации интерфейса MPI. Полученные теоретические результаты следует подтвердить созданием параллельного алгоритма и соответствующей программы с отладкой на параллельном кластере.

Ожидаемые результаты Курсовая работа должна содержать подробную разработку метода и алгоритма распараллеливания аппроксимаций Куранта и Зламала в двумерном случае для параллельной системы с использованием интерфейса MPI и оценить необходимый объем памяти и необходимое число тактов при определенных предположениях о параллельной системе и о характеристиках рассматриваемой реализации интерфейса MPI в зависимости от значения векторного параметра µ с иллюстрацией результатов на параллельном кластере.

В дипломной работе (продолжение курсовой) необходимо обобщить полученные в курсовой работе результаты на трехмерный случай, т.е.

дать подробную разработку метода и алгоритма распараллеливания вычислений аппроксимаций Куранта и Зламала в трехмерном случае для параллельной системы с использованием интерфейса MPI и оценить необходимый объем памяти и необходимое число тактов при определенных предположениях о параллельной системе и о характеристиках рассматриваемой реализации интерфейса MPI. Полученные теоретические результаты следует подтвердить созданием параллельного алгоритма и соответствующей программы с отладкой на параллельном кластере.

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

[6], c. 14-21). Могут быть также детализированы характеристики рассматриваемого класса ПВС (иерархическая структура памяти ПВС, способы кэшировнания и т.п.) Рекомендации по чтению дополнительной литературы Рекомендуется первоначально читать литературу в такой последовательности [1] Михлин С.Г., Смолицкий Х.Л. Приближенные методы решения дифференциальных и интегральных уравнений. СМБ. М.,1965.

[2] Сиарле Ф. Метод конечных элементов для эллиптических задач.

М., 1980.

[3] www.parallel.ru [4] Корнеев В.В. Параллельные вычислительные системы. М., 1999.

[5] Воеводин В.В., Воеводин Вл.В.. Параллельные вычисления. СПб, 2002.

[6] Демьянович Ю.К. Аппроксимация на многообразии и минимальные сплайны. СПб, 1994.

КУРСОВАЯ (ДИПЛОМНАЯ) РАБОТА

Введение в стандарт MPI-2: основные направления модификаций Введение в проблему При создании вычислительных систем (ВС) на определенном этапе возникает вопрос об их оснащении математическим обеспечением, которое позволяло бы в дальнейшем эффективно использовать ВС на практике. Для решения сверхсложных задач соэдаются высокопроизводительные вычислительные системы. Современные технологии сохдания процессоров не позволяют в дальнейшем существенно наращивать их быстродействие. Поэтому основное направлением в разработке новых высокопроизводительных ВС является увеличение числа параллельно работающих процессоров. Все мощные современные вычислительные системы представляют собой компьютеры (ПВС) с параллельной архитектурой (см. регулярно публикуемый в интернете список TOP500, содержащий характеристики 500 наиболее мощных вычислительных систем). Для программирования для таких ВС требуются специальные программные средства, позволяющие автоматизированно распределять работу по упомянутым процессорам. Возникает задача создания методов, допускающих распараллеливание, и алгоритмов, приспособленных для эффективного выполнения на параллельной вычислительной системе (ПВС). Во многих случаях эта задача облегчается тем, что каждая параллельная система снабжается средствами параллельного программирования; в большинстве случаев это интерфейс MPI Message Passing Interface, реализованный на параллельных системах обычно в языках C, C ++ и F ortran в виде библиотеки процедур. Использование этого стандарта в значительной степени гарантирует переносимость и масштабируемость (т.е. независимость программы от числа используемых процессоров и других устройств); таким образом, полученную программу можно использовать на других параллельных системах.

В случае использования ПВС дополнительно возникают вопросы:

a) возможно ли распараллелить вычислительный процесс, b) каковы характеристики вариантов распараллеливания с точки зрения используемой ПВС (объем необходимой памяти, число тактов, загруженность системы и т.п.) c) какие задачи предполагается решать на ПВС (каков класс задач), d) как определить "наилучший" из вариантов (или что считать "наилучшим" вариантом).

Постановка задачи Требуется 1) ознакомиться с основными характеристиками стандарта MPI- (см. [1], с. 105-130, а также соответствующие разделы в [2-3]), 2) изучить основные направления модификаций стандарта MPI-1 при разработке стандарта MPI-2 (см. [4], с. 1-20), 3) предложить свои варианты усовершенствования стандарта 4) продемонстрировать программные реализации решения СЛАУ общего вида с использованием различных вариантов стандарта и дать сравнительный анализ полученных результатов Ожидаемые результаты Курсовая работа должна содержать подробную разработку пунктов 1) и 2) предложенного заданя В дипломной работе (продолжение курсовой) следует реализовать также и пункты 3) – 4). Полученные теоретические результаты следует проиллюстрировать на работающей программе для параллельного кластера.

Дальнейшее развитие результатов состоит в разработке программной модели предложенного варианта для параллельного кластера и в формулировке полученных результатов для Message Passing Interface Forum.

[1] Немнюгин С., Стесик О. Параллельное программирование для многопроцессорных вычислительных систем. СПб. [2] Корнеев В.Д. Параллельное программирование в MPI. МоскваИжевск. 2003.

[3] Воеводин В.В., Воеводин Вл.В.. Параллельные вычисления. СПб, 2002.

[4] MPI-2: Extensions to the Message-Passing Interface (Message Passing Interface Forum, July 18, 1997) - на дискете

КУРСОВАЯ (ДИПЛОМНАЯ) РАБОТА

Введение Стандарт MPI-2 появился в 1998 году; он явился развитием стандарта MPI. Функции нового стандарта значительно расширены. Основные изменения по сравнению с предыдущими версиями таковы: 1) предусмотрено динамическое порождение процессов, 2) между любыми процессами можно устанавливать связь, 3) возможно одностороннее взаимодействие процессов (схема put/get), 4) предусмотрен параллельный ввод/вывод.

Одной из важных задач, поставленных при создании стандарта MPIявляется защита данных от случайного (или несанкционированного) изменения. Для этого разработан механизм доступа к данным и механизм предупреждения и исправления ошибок.

Постановка задачи В данной работе требуется изучить упомянутые механизмы защиты данных (курсовая работа) и предложить дополнительные способы и процедуры, позволяющие усилить защиты данных при динамическом порождении процессов, при установлении связей между процессами, при параллельном вводе/выводе (дипломная работа).

Ожидаемые результаты Курсовая работа должна содержать подробное изложение средств защиты данных от случайного (или несанкционированного) изменения, представленных разработчиками стандарта MPI-2.

В дипломной работе необходимо разработать дополнительные средства защиты данных (и программ) с обоснованием их необходимости и эффективности и представить их на Forum. Может быть также представлены компьютерные программы моделирования упомянутых средств на примере интерфейса MPI-1.

Рекомендации по изучению литературы Для курсовой работы 1) [1], с. 1-2, 5-20, 42, 61-64;

Для дипломной работы 1) [1], с. 81-101, 109-112, 136-137, 223-240, 265-268;

2) [2], с. 78-92.

3) [3], обзор сайта Рекомендуемая литература [1] MPI-2: Extensions to the Message Passing Interface. MPI Forum.

1997.

[2] MPI-2: Journal of Development. MPI Forum. 1997.

[3] http://www.mpiforum.org

КУРСОВАЯ (ДИПЛОМНАЯ) РАБОТА

PVM параллельная виртуальная машина, методы реализации параллельных программ Введение в проблему Для решения сверхсложных задач соэдаются высокопроизводительные вычислительные системы. Основное направлением в разработке новых высокопроизводительных ВС является увеличение числа параллельно работающих процессоров. Все мощные современные вычислительные системы представляют собой компьютеры (ПВС) с параллельной архитектурой (см. регулярно публикуемый в интернете список TOP500, содержащий характеристики 500 наиболее мощных вычислительных систем). Для программирования для таких ВС требуются специальные программные средства, позволяющие автоматизированно распределять работу по упомянутым процессорам. Вообще всегда при создании вычислительных систем (ВС) на определенном этапе возникает вопрос об их оснащении математическим обеспечением, которое позволяло бы в дальнейшем эффективно использовать ВС на практике; в данном случае появляется задача создания таких методов, которые допускают распараллеливание, и таких алгоритмов, которые приспособлены для эффективного выполнения на ПВС. Во многих случаях эта задача облегчается тем, что каждая параллельная система снабжается средствами параллельного программирования; в большинстве случаев это интерфейс MPI Message Passing Interface, реализованный на параллельных системах обычно в языках C, C ++ и F ortran в виде библиотеки процедур. Однако, для решения ряда задач важным оказывается стандарт PVM Parallel Virtual Machine, изучению и использованию которого предлагается посвятить данную работу. Применение этого стандарта в значительной степени гарантирует переносимость и масштабируемость (т.е. независимость программы от числа используемых процессоров и других устройств); таким образом, полученную программу можно использовать на других параллельных системах.

Постановка задачи Требуется 1) ознакомиться с основными характеристиками стандарта PVM и дать сравнение с MPI (см. [1], с. 235-275 и [2], с.164, 180), 2) изучить основные способы программирования с использованием PVM (см. [1], с.275-306), 3) предложить свои варианты усовершенствования стандартов стандарта PVM, 4) дать программные реализации решения СЛАУ общего вида с использованием стандартов MPI и PVM; провести отладку и представить сравнительный анализ полученных результатов.

Ожидаемые результаты Курсовая работа должна содержать подробную разработку пунктов 1) и 2) предложенного задания В дипломной работе (продолжение курсовой) следует реализовать также и пункты 3) – 4). Полученные теоретические результаты следует проиллюстрировать на работающих программах для параллельного кластера.

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

[1] Немнюгин С., Стесик О. Параллельное программирование для многопроцессорных вычислительных систем. СПб. 2002.

[2] Корнеев В.В. Параллельные вычислительные системы. Москва.

1999.

КУРСОВАЯ РАБОТА

Составление экспертного заключения из языков программирования: F ortran90, Ada95, C + +, Java Экспертное заключение должно содержать обзор достоинств и недостатков выбранного языка программирования. В качестве базового плана для данного обзора предлагается следующий:

• Читабельность программ.

• Легкость их написания.

• Надежность программирования.

• Простота/ортогональность.

• Удобство управляющих структур.

• Поддержка параллельного программирования.

• Поддержка абстракции данных.

• Проверка типов.

• Поддержка объектно-ориентированной технологии.

• Расширяемость.

• Объем стандартной библиотеки.

• Объем доступных библиотек.

Литература:

[1] Роберт У. Себеста, Основные концепции языков программирования, Изд. дом "Вильямс", 2001.

+ литература по выбранному языку программирования

КУРСОВАЯ РАБОТА

Написание лексического анализатора для нового языка программирования Лексический анализатор программа, превращающая поток входных символов в поток токенов, т. е. (грубо говоря) номеров лексических понятий идентификаторов, ключевых слов, констант и т. п. Задача состоит в написании программы самоизменяющегося конечного автомата, выдающего по входному потоку символов выходной поток токенов.

Литература:

[1] А. Ахо, Р. Сети, Дж. Ульман, Компиляторы: принципы, технологии, инструменты, М.: Изд. дом "Вильямс", 2001.

КУРСОВАЯ РАБОТА

Написание синтаксического анализатора для нового языка программирования Синтаксический анализатор программа, которая преобразует поток токенов, полученный на выходе лексического анализатора, в дерево синтаксического разбора, указывающего на порядок применения отдельных операций. Задача состоит в написании синтаксического анализатора приоритета операций (т. е. ориентирующегося в основном на приоритет операций), однако она осложняется тем, что приоритет операций определяется динамически во входном потоке токенов.

Литература:

[1] А. Ахо, Р. Сети, Дж. Ульман, Компиляторы: принципы, технологии, инструменты, М.: Изд. дом "Вильямс", 2001.

КУРСОВАЯ РАБОТА

Написание семантического анализатора для нового языка программирования Семантический анализатор программа, проставляющая на дереве синтаксического разбора реальные типы подвыражений и реально вызываемые функции для каждой операции. Для языка программирования, о котором идет речь, данная фаза анализа требует разбора контекстно-свободной грамматики, и речь идет о реализации известного алгоритма с использованием динамического программирования.

Литература:

[1] А. Ахо, Р. Сети, Дж. Ульман, Компиляторы: принципы, технологии, инструменты, М.: Изд. дом "Вильямс", 2001.

КУРСОВАЯ РАБОТА

Написание подсистемы вызова функций времени компиляции Функции времени компиляции функции, вызов которых происходит во время компиляции. Данная концепция представляет собой обобщение стандартного аппарата макросредств вроде шаблонов C + + и позволяет использовать для таких функций все имеющиеся библиотеки.

Задача состоит, во первых, в обеспечении полного цикла вызова такой функции (компиляция компоновка запуск), и, во-вторых, в обеспечении связи между компилятором с одной стороны и средой выполнения такой функции, с другой стороны.

Литература:

[1] А. Ахо, Р. Сети, Дж. Ульман, Компиляторы: принципы, технологии, инструменты, М.: Изд. дом "Вильямс", 2001.

ДИПЛОМНАЯ РАБОТА

Написание подсистемы ввода-вывода Подсистема ввода-вывода, как и вся стандартная библиотека, должна быть организована на общих принципах контейнерных классов. Задача состоит в (грубо говоря) смене интерфейса стандартной библиотеки C + + с потокового на контейнерно-классовый (поскольку реализация планируется на C ++). Планируется организация интерфейса подобного типа не только для традиционного ввода-вывода, но и для специализированных устройств типа звуковых карт и т. п.

Литература:

[1] Б. Страуструп, Язык программирования C++, спец. изд., М.;

СПб.: "Изд-во БИНОМ" - "Невский Диалект", 2002.