- •Оглавление
- •Глава 1. Архитектура вычислительных систем 11
- •Глава 2. Реализация параллельных алгоритмов 63
- •Глава 3. Надежность и живучесть вычислительных систем 96
- •Глава 4. Библиотека параллельных программ 120
- •Глава 5. Граф-схемы параллельных алгоритмов 150
- •Глава 6. Исследование информационных граф-схем со скалярными весами для планирования параллельных вычислений 182
- •Глава 7. Исследование информационных граф-схем решаемых задач с векторными весами для планирования параллельных вычислений 204
- •1.Количественные характеристики, применяемые для оценок параметров вычислительных систем
- •Глава 1. Архитектура вычислительных систем
- •Для случая неоднородной системы номинальное быстродействие выразится как
- •Здесь – вероятность выбора j-й операции, , . Для однородной вс её быстродействие по Гибсону выразится соотношением
- •Для неоднородной вс это быстродействие может быть определено, как
- •1.1.1. Вопросы к разделу 1.1.
- •2.Понятие о современных вычислительных системах
- •Пример графа регулярной вычислительной системы представлен на рисунке 1.2.1.
- •Примечание: Для регулярной вычислительной системы
- •2.1. Вопросы к разделу 1.2.
- •3.Структура современных вычислительных систем
- •3.1.Схема обмена с помощью структуры «Общая шина»
- •3.2.Схема обмена с помощью структуры «Линейка»
- •3.3.Вычислительная система, имеющая структуру типа «Кольцо»
- •3.4.Схема обмена с помощью структуры типа «Решётка»
- •1.3.5. Схема обмена с помощью структуры типа «Двумерный тор»
- •3.1.Схема обмена с помощью структуры типа «n-мерный двоичный гиперкуб» или «nD-куб»
- •3.2.Реализация обмена с помощью структуры типа «Обобщенный nD-куб»
- •3.3.Структура вс типа «n-мерный обобщённый тор»
- •3.4.Структура вс с сетью типа «Циркулянт»
- •1.3.10. Вычислительная система «Максимальный обхват»
- •1.3.11. Вычислительные системы со структурой сетей типа «Симметричные графы»
- •На рисунке 1.3.11. Представлена вс с симметричным графом.
- •1.3.12. Вычислительные системы с сетью связей типа «Гомоморфные графы»
- •1.3.13. Вычислительные системы с сетью связей типа «Граф л(n,V,g)»
- •1.3.14. Структура вычислительной системы типа «Бинарное дерево t0(n) глубины n»
- •1.3.15. Структура вычислительной системы типа «Мультидерево глубины n и ширины k t1(n,k)»
- •3.5. Вопросы к разделу 1.3
- •4.Коммуникационные среды вычислительных систем
- •Коммуникационная среда должна удовлетворять следующим требованиям:
- •4.1.Коммуникационная среда на основе масштабируемого когерентного интерфейса sci
- •4.2.Коммуникационная среда на основе технологии Myrinet
- •1.4.3. Краткая характеристика коммуникационной среды QsNet II
- •4.3. Вопросы к разделу 1.4
- •5.Коммутаторы вычислительных систем
- •1.5.1. Типы коммутаторов
- •5.1. Управление коммутаторами
- •5.2. Алгоритмы определения маршрутов
- •5.3. Дедлоки в составных коммутаторах
- •5.4.Вопросы к разделу 1.5
- •6.Процесс функционирования вычислительных систем
- •6.1. Вопросы к разделу 1.6.
- •7.Принципы технической реализации вс
- •1.7.1. Вопросы к разделу 1.7
- •1.8. Архитектурные особенности вс
- •1.8.1. Архитектурные свойства вс
- •1.8.2. Схема обмена информацией между ветвями параллельных алгоритмов
- •7.1.Опыт применения методики крупноблочного распараллеливания сложных задач
- •7.2.Архитектурные аспекты при создании ос вс
- •7.3.Структурные характеристики вс
- •7.4.Классификация структур вс
- •7.5.Вопросы к разделу 1.8.
- •Глава 2. Реализация параллельных алгоритмов
- •2.1. Реализация параллельных алгоритмов
- •2.1.1. Определение параллельного алгоритма
- •7.6.Организация динамического распараллеливания в суперскалярных микропроцессорах
- •2.1.3. Предварительная выборка команд и предсказание переходов
- •7.7.Декодирование команд, переименование ресурсов и диспетчеризация
- •7.8.Исполнение команд
- •2.1.6. Работа с памятью
- •2.1.7. Завершение выполнение команды
- •2.1.8. Направления развития суперскалярной архитектуры
- •7.9.Мультитредовая модель выполнения программы
- •7.10.Аппаратные и программные средства, необходимые для мультитредовой архитектуры
- •2.1.11. Специфика мультитредовых моделей распараллеливания
- •2.1.12. Вопросы к разделу 2.1
- •2.2.Организация распараллеливания на уровне программных модулей
- •2.2.1. Примеры организации вычислений на уровне программных модулей
- •2.2.2. Решение системы линейных уравнений методом Гаусса с помощью вс типов «решётка» и «линейка»
- •2.2.3. Исполнение алгоритма Гаусса на «решётке» n*n вm
- •2.2.4. Исполнение алгоритма Гаусса на «линейке», состоящей из n вм
- •2.2.5. Показатели эффективности параллельных алгоритмов
- •2.2.6. Понятие о сложных задачах
- •2.2.7. Вопросы к разделу 2.2
- •Глава 3. Надежность и живучесть вычислительных систем
- •8.Основные задачи создания отказоустойчивых систем
- •8.1.Вопросы к разделу 3.1
- •9.Классификация типов отказоустойчивости сложных систем и ее критерии
- •9.1.Вопросы к разделу 3.2
- •10.Способы обеспечения отказоустойчивого функционирования вс
- •3.3.1. Диагностическое тестирование вс
- •3.3.3. Способы восстановления отказоустойчивых вс
- •10.1.Вопросы к разделу 3.3
- •3.4. Построение живучих вс на основе экспоненциально- надежностного подхода
- •3.4.1. Показатели надежности вс
- •10.2. Методика расчета показателей надежности вс
- •3.4.3. Живучесть вс
- •3.4.4. Вопросы к разделу 3.4
- •11.Построение живучих вс, работоспособных в расчетном диапазоне кратностей отказов
- •3.6.1. Горячий резерв
- •3.6.2. Репликация
- •3.6.3. Кластеры высокой готовности
- •3.5.1. Вопросы к разделу 3.5
- •3.6. Реализация модели отказоустойчивых систем
- •4.1.2. Принципиальная схема программирования в OpenMp
- •11.2. Описание основных конструкций open mp
- •4.1.4. Способы построения параллельных программ
- •4.1.6. Вопросы к разделу 4.1
- •4.2. Основы построения библиотеки mpi
- •4.2.1. Основные понятия
- •4.2.2. Структура программ в mpi
- •4.2.3. Определение структуры приходящего сообщения
- •4.2.4. Определение базовых характеристик коммуникационной сети
- •11.4.Анализ тупиковых ситуаций при обмене
- •4.2.6. Организация передачи-приёма сообщений без блокировки
- •4.2.7. Реализация отложенных запросов на взаимодействие
- •4.2.8. Сравнительная оценка различных способов обмена данными
- •4.2.9. Использование глобальных операций в mpi
- •4.2.10. Взаимодействие процессов в mpi
- •4.2.11. Вопросы к раделу 4.2
- •Глава 5. Граф-схемы параллельных алгоритмов
- •5.1. Представление параллельных алгоритмов в виде граф-схем
- •5.1.1. Преобразование последовательных алгоритмов в параллельные
- •5.1.2.Использование граф-схем для представления параллельных алгоритмов
- •5.1.3. Вопросы к разделу 5.1
- •5.2.1. Вычисление матриц следования, расширенных матриц следования и матриц следования с транзитивными связями
- •5.2.2. Вопросы к разделу 5.2
- •11.5.Построение матрицы логической несовместимости.
- •5.3.2. Построение матрицы логической несовместимости операторов
- •5.3.3. Вопросы к разделу 5.3
- •5.4.1. Построение множеств взаимно независимых операторов.
- •5.4.2. Вопросы к разделу 5.4
- •Глава 6. Исследование информационных граф-схем со скалярными весами для планирования параллельных вычислений
- •6.1. Численные характеристики информационных граф-схем со скалярными весами
- •6.1.1 Определение ранних и поздних сроков окончания выполнения операторов.
- •11.6.Определение функций плотности загрузки, и минимальной загрузки для информационных граф-схем
- •6.1.3. Вопросы к разделу 6.1
- •6.2.1. Распределение операторов по вм вычислительной системы с общим полем памяти для информационной граф-схемы
- •6.2.2. Распределение операторов по вм вычислительной системы с общим полем памяти для информационно-логической граф-схемы
- •При срабатывании условного оператора «один», дуги 1.1 требуется 10 вм. Время решения задачи составит 22 условные единицы.
- •6.2.3. Распределение операторов по вм вычислительной системы с распределённой памятью для информационной граф-схемы
- •6.2.4. Реализация диаграмм для общепринятых способов обмена данными между вм вычислительной системы с распределённой памятью для информационной граф-схемы
- •6.2.5. Вопросы к разделу 6.2
- •Глава 7. Исследование информационных граф-схем решаемых задач с векторными весами для планирования параллельных вычислений
- •7.1 Информационная граф-схема решаемых задач с векторными весами вершин
- •7.1.1 Понятие об неоднородных системах
- •7.1.2. Основные определения, используемые для неоднородных вс
- •7.1.3. Вопросы к разделу 7.1
- •Литература
7.1.3. Вопросы к разделу 7.1
1. В чём преимущества и недостатки неоднородных вычислительных систем?
2. С какой целью осуществляется преобразование векторных граф-схем в набор скалярных граф- схем?
3. Покажите на примере полезность от применения теоремы 7.1.1.
4. Когда может быть полезна G выборка граф-схемы G*?
5. В чём отличие определений плотностей загрузок для однородной и неоднородной ВС?
6. Объясните, почему согласно рисунку 7.1.4 Z1(2, 5, 6, 5, 8, 1, 6)=2, а Z2(2, 5, 6, 5, 8, 1, 6)=5.
7. Объясните, почему в алгоритме 7.1.2 в пункте 3 взяты те же интервалы, что и в пункте 2 алгоритма 6.1.4.
Литература
1. Хорошевский В.Г. Архитектура вычислительных систем. Изд. МГТУ им. Баумана, Москва, 2005 г. 511 с. : ил.
2. Корнеев В. В. Параллельные вычислительные системы. -М.: Гелиос АРВ,2004. -487 с. : ил.
3. Барский А. Б. Параллельные процессы в вычислительных системах. - М.: Радио и связь, 1990 - 256с. : ил.
4. Водяхо А.И., Горнец Н.Н., Пузанков Д.В. Высокопроизводительные системы обработки данных. -М.: Высшая школа. 1997. - 150с. : ил.
5. http://www.specbench.org/osg/cpu2000/results/.
6. http://www.netlib.org/benchmark/performance.ps.
7. http://www.top500.org.
8. ScaLAPACK. http://www.netlib.org./scalarpack/scalarpack_home.html.
9. Petitet A., Whaley R., Dongarra J., Cleary A. HPL – A Portable Implementation of the High – Performance Linpack Benchmark for Distributed – Memory Computers. http://www.netlib.org/master_counts2.html#benchmark/hpl.
10. Batcher K. STARAN Parallel Processor System Hardware. NCC . Pp. 405-410, 1974.
11. Амамия М., Танака Ю. Архитектура ЭВМ и искусственный интеллект.- М.: Мир. 1993. 397 с.
12. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. Санк-Петербург: БХВ-Петербург, 2002.-600с. : ил.
13. Tera Computer Company Completes Desing of Breakthrough Multiprocessor Chip. http://www.tera.com.
14. Exemplar SPP1000 System. Technical Summary. Convex Computer Corporation, 3000 Waterview Parway, P.O.BOX 833851,Richardson, Texas 75083-3851, 1994.p.25.
15. ZabrodinA.V., Levin V.K., Korneev V.V. The massively parallel computer system MBC-100. – Lecture Notes in computer Science, № 964. Parallel Computing Technologies. Third International Conference, PaCT – 95, s - Petersburg, Russia, Sept. 1995, Springer. Pp. 341-355/
16. Smith J.E. Decoupled access/execute computer architectures. Proc. of IEEE.Pp.112-119,1983.
17. Sohi G., Roth A. Speculative Multithreaded Processor. Computer. Vol. 34. 2005. - № 4.
18. Hennessy J. The Future of Systems Research. Computer. Pp.27-33.1999.-№ 8.
19. IEEE. Computer Society.IEEE Standart for Scalable Coheren Interface (SCI). IEEE Std 1596-1992. New-York, August, 1993.
20. http://www.myri.com.
21. http://www.quadrics.com.
22. Kol R., Ginosar R. Kin: A High Perfomance Asynchronous Processor Architecture. Proc. of International Conference on Supercomputing. Pp. 433-440. July 13-17, 1998, Melbourne, Australia.
23. http://parallel.ru/tech/tech_dev/par_libs.html
24. http://www.kai.com/parallel/kappro/guide/
Фадеев Д.К., Фадеева Д.Н. Вычислительные методы линейной алгебры. – М.: Физматгиз, 1960. С. 656.
Кун С. Матричные процессоры на СБИС. – М.: Мир, 1995. С. 672.
27. Седухин С. Г. Параллельно-поточная интерпретация метода Гаусса. Вычислительные системы с программируемой структурой. (Вычислительные системы 94). – Новосибирск: ИМ СОАН СССР, 1982. С. 70-80.
28. http://parallel.ru/tech/tech_dev/mpi.html
29. Антонов А.С. Параллельное программирование с использованием технологии MPI: Учебное пособие. –М.: Изд-во МГУ, 2004.-71 с.
30. Криницкий Н.А., Миронов Г.А., Фролов Г.Д. Программирование и алгоритмические языки. –М.: Физматгиз, 1979.-509 с.
31. Фаронов В.В. TurboPascal 7.0. Практика программирования. Учебное пособие. –М.: «Нолидж», 1997.-432 с., ил.
32. Корн Г., Корн Т. Справочник по математике для научных работников и инженеров. –М.: Физматгиз, 1973.-832 с.
33. Ильин В.П.. Методы неполной факторизации для решения алгебраических систем. – М.: Наука, 1995. – 287 с.
34. Старченко А.В. // Вестник Томского государственного университета.− 2003. − №10. − С. 70−80.
35. Данилкин Е.А. // Третья Сибирская школа-семинар по параллельным вычислениям / Под ред. проф. А.В. Старченко. Томск: Изд-во Том. ун-та, 2006. С. 95 – 101.