Скачать 254.51 Kb.
|
Содержание Внимание - местами могут быть неверно распознанные слова. А английские слова могут стать русскими: Open = Орет. (такое нашел и поправил уже). Предисловие 1 Много ли надо знать о параллельных вычислениях? 1 Часть I. Параллельные вычислительные системы 11 Глава 1. Что скрывают "обыкновенные" компьютеры 13 § 1.1. Немного об устройстве компьютера 14 Представление информации. Общее устройство компьютера. Операции и операн- ды. Команды. Управление. Арифметико-логическое устройство. Память. Устройст- во ввода/вывода. Центральный процессор. Вопросы и задания. § 1.2. Операции с числами 19 Двоичное представление чисел. Разряды. Фиксированная и плавающая запятая. Округление чисел. Ошибка округления. Сравнение представлений чисел. Вопросы и задания. § 1.3. Иерархия памяти 25 Различные виды памяти. Время доступа. Виртуальная память. Влияние на время решения задачи. Трудности работы с медленной памятью. Вопросы и задания. § 1.4. Языки программирования и программы 31 Языки низкого и высокого уровня. Проблемно-ориентированные языки. Контроль эффективности программ. Компьютерная зависимость. Портабельность программ. Компиляторы и эффективность программ. Необходимость привлечения дополни- тельной информации. Вопросы и задания. § 1.5. Узкие места 37 Иллюстративная модель компьютера. Пиковая и реальная производительность. Взаимодействие отдельных узлов компьютера. Эффективность. Узкие места. Во- просы и задания. Глава 2. Как повышают производительность компьютеров 42 § 2.1. Усложнение и наращивание аппаратных средств 43 Уменьшение размеров. Скалярная, конвейерная и параллельная обработка. Иерар- хия памяти. Опережающий просмотр команд. Локальность вычислений и исполь- зования данных. Примеры. Вопросы и задания. § 2.2. Повышение интеллектуальности управления компьютером 60 Закон Мура. Спецпроцессоры. Суперскалярные и VLIW-архитектуры. Коммутацион- ные схемы. Топологии связей процессоров. SMP-компьютеры. Архитектуры NUMA и ccNUMA. Развитие программного обеспечения. Примеры. Вопросы и задания. Содержание § 2.3. Система функциональных устройств _ 78 Простые и конвейерные устройства. Стоимость работы. Загруженность. Пиковая и реальная производительность. Эффективность. Различные соотношения. Законы Амдала и Густавсона—Барсиса. Взаимосвязь законов. Вопросы и задания. Глава 3. Архитектура параллельных вычислительных систем 94 § 3.1. Классификация параллельных компьютеров и систем 96 Классификация Флинна, Хокни, Фенга, Хендлера, Шнайдера, Скилликорна. Взаимосвязь классификаций. Архитектура компьютеров и структура задач. Вопро- сы и задания. § 3.2. Векторно-конвейерные компьютеры 114 Детальное рассмотрение компьютера Cray С90. Структура оперативной памяти. Регистровая структура. Функциональные устройства. Пиковая и реальная произво- дительность. Вопросы и задания. § 3.3. Параллельные компьютеры с общей памятью 134 Детальное рассмотрение компьютера HP Superdome. Ячейка компьютера. Локальные и удаленные ячейки. Процессор PA-8700. Работа с памятью. Вопросы и задания. § 3.4. Вычислительные системы с распределенной памятью 142 Детальное рассмотрение компьютеров Cray T3D/T3E. Управляющие и вычисли- тельные узлы. Процессорный элемент. Сетевой интерфейс. Сетевой маршрутиза- тор. Коммуникационная сеть. Память. Кластерные проекты. Вопросы и задания. § 3.5. Концепция GRID и метакомпьютинг 154 Метакомпьютер как огромная распределенная система. Особенности распределе- ния задач и передачи данных. Различные проекты. Концепция GRID. Проблемы пользователей. Вопросы и задания. § 3.6. Производительность параллельных компьютеров 162 Сравнение вычислительных систем. Пиковая производительность и формат дан- ных. Вычислительные и коммуникационные ядра. Тесты. Вопросы и задания. Часть П. Параллельное программирование 179 Глава 4. Большие задачи и параллельные вычисления 181 § 4.1. Большие задачи и большие компьютеры 183 Моделирование климатической системы. Обтекание летательных аппаратов. Ма- тематические модели и вычислительная техника. Огромные объемы вычислений и размеры памяти. Вопросы и задания. § 4.2. Граф алгоритма и параллельные вычисления 191 Порядок вычислений. Граф алгоритма. Параллельные формы графа. Ярус и высо- та. Инвариантность к ошибкам округления. Граф алгоритма и информационное ядро. Параметризация в графе. Вопросы и задания. § 4.3. Концепция неограниченного параллелизма 198 Параллельные алгоритмы. Принцип сдваивания. Примеры алгоритмов малой вы- соты. Ограниченность концепции. Новые алгоритмы — новые свойства. Трудности в проблеме портабсльности. Вопросы и задания. § 4.4. Внутренний параллелизм 206 Преимущества внутреннего параллелизма. Примеры. Обнаружение новых свойств. Декомпозиция алгоритмов. Использование мешенной памяти. Структура алгорит- мов и программ. Вопросы и задания. Содержание V Глава 5. Технологии параллельного программирования 219 § 5.1. Использование традиционных последовательных языков 221 Обилие средств параллельного программирования. Трудности применения. Необ- ходимость дополнительной информации. Системы программирования OpenМР, DVM, mpC. Примеры использования. Вопросы и задания. § 5.2. Системы программирования на основе передачи сообщений 268 Системы параллельного программирования Linda, MPI, MPI-2. Интерфейсы для последовательных языков Fortran, С, С++. Примеры использования. Вопросы и задания. § 5.3. Другие языки и системы программирования 301 Т-система. Система программирования НОРМА. Приближенность к математиче- ским записям. Примеры использования. Вопросы и задания. Глава 6. Тонкая информационная структура программ 320 § 6.1. Графовые модели программ 324 Информационная структура программы. Операционная и информационная связь. Графы управления, операционно-логической истории, информационный, истории реализации, зависимостей, влияния. Минимальные графы зависимостей. Снова граф алгоритма. Примеры графов. Вопросы и задания. § 6.2. Выбор класса программ 337 Статический анализ структуры программ. Статистическая значимость отдельных операторов. Линейный класс программ. Вопросы и задания. § 6.3. Графы зависимостей и минимальные графы 342 Опорные оператор, гнездо циклов, область. Пространства итераций. Лексикографи- ческий порядок. Типы зависимостей. Максимальный и минимальный графы зависи- мостей и их свойства. Теорема об информационном покрытии. Вопросы и задания. § 6.4. Простые и элементарные графы 351 Простые и элементарные графы и программы. Расщепление минимальных графов на простые. Погружение минимального графа в объединение элементарных. Све- дение к анализу элементарных программ. Вопросы и задания. § 6.5. Лексикографический порядок и L-свойство матриц 355 Лексикографический максимум в многограннике, L-свойство матриц. Критерий лек- сикографического максимума. Дополнительные свойства матриц с L-свойством. Вопросы и задания. § 6.6. Построение минимальных графов зависимостей 363 Основная задача. Конструктивные алгоритмы построения элементарных, простых и минимальных графов зависимостей для программ из линейного класса. Вопросы и задания. § 6.7. Циклы ParDO и избыточные вычисления 373 Лексикографически правильные графы. Параллельные множества. Параллельная структура программ. Критерий цикла ParDO. Избыточные вычисления и критерий их обнаружения. Вопросы и задания. § 6.8. Примеры 378 Формализованное построение графов алгоритмов для конкретных программ. Сложнейшие графы алгоритмов для простейших программ. Зависимость парал- лельной структуры от порядка выполнения операций. VI Содержание Глава 7. Эквивалентные преобразования программ 393 § 7.1. Развертки графа 394 Строгая и обобщенная развертки. Свойства разверток. Развертки и параллельные множества. Конструктивный алгоритм построения кусочно-линейных разверток. Выделение в графах строгих и нестрогих зависимостей. Вопросы и задания. § 7.2. Макрографы зависимостей 404 Макровершины и макродуги. Укрупненное представление зависимостей. Разверт- ки и декомпозиция алгоритмов. Распределенные вычисления. Работа с медленной памятью. Вопросы и задания. § 7.3. Эквивалентные программы 408 Эквивалентные преобразования программ. Эквивалентные по вычислениям про- граммы. Преобразования, гарантирующие эквивалентность. Вопросы и задания. § 7.4. Наиболее распространенные преобразования программ 415 Перестановка циклов. Слияние циклов. Переупорядочивание операторов. Распре- деление цикла. Скашивание цикла. Расщепление пространства итераций. Выпол- нение итераций цикла в обратном порядке. Треугольные преобразования. Вопросы и задания. § 7.5. Две сопутствующие задачи 421 Оценивание длины критического пути графа зависимостей. Распределение масси- вов по модулям памяти. § 7.6. Примеры 426 Формализованное построение разверток и макрографов для конкретных программ. Определение циклов ParDO. Распределение массивов по модулям памяти. Эквива- лентное преобразование подпрограммы OLDA из пакета тестов Perfect Club Benchmarks. Самые лучшие результаты. Система V-Ray. Часть III. Смежные проблемы и применение 441 Глава 8. Вычислительные системы и алгоритмы 443 § 8.1. Расширение и уточнение линейного класса 448 Прямая подстановка. Вычисляемый цикл go to. Вычисляемые ветвления. Нелиней- ные индексные выражения. Уточнение описания внешних переменных. Подпро- граммы и функции. Функции min и max. Прямое вычисление графов. Вопросы и задания. § 8.2. Граф-машина 459 Локальность управления. Свойства различных реализаций. Гомоморфная свертка. Граф-машина и граф вычислительной системы. Сохранение временных режимов. Вопросы и задания. § 8.3. Регулярные и направленные графы 471 Итерационные процессы и регулярные графы. Расщепление бесконечного регу- лярного графа. Главный регулярный подграф. Критерий отсутствия контуров. Ли- нейные развертки регулярного графа. Гомоморфная свертка регулярных графов. Вопросы и задания. § 8.4. Математические модели систолических массивов 482 Систолические массивы как вычислительные системы. Локальность управления. Минимальные коммуникационные связи. Реализация регулярных графов алгорит- мов. Примеры построения систолических массивов для заданных алгоритмов. Во- просы и задания. Содержание VII § 8.5. Математическая модель алгебраического вычислителя 499 Структура алгебраических задач. Спецпроцессор для алгебраических задач. Ис- пользование систолического массива для матричной операции А + ВС. Вопросы и задания. § 8.6. Матрицы и структура алгоритмов 503 Общие вычислительные процессы. Вариационная матрица алгоритма. Матрицы смежностей и инциденций. Критерий развертки. Уравновешенные графы. Крите- рий уравновешенности. Вопросы и задания. § 8.7. Новое применение сведений о структуре 511 Восстановление линейного функционала. Вычисление градиента. Анализ ошибок округления. Всюду вариационная матрица алгоритма. Вопросы и задания. § 8.8. Примеры 528 Техника ускоренного вычисления градиента функции. Выполнение анализа оши- бок по формальным правилам. Нахождение малых относительных эквивалентных возмущений. Глава 9. Пользователь в среде параллелизма 533 § 9.1. Типичные ситуации в вопросах и ответах 534 Конкретные вопросы из практики параллельного программирования. Исследова- ние возникших ситуаций. Возможные идеи и пути решения. Что следует из пере- численных примеров? Вопросы и задания. § 9.2. Программный сервис в параллельных вычислениях 558 Почему в программе что-то не так? Компиляторы, отладчики, профилировщики, анализаторы, конверторы. Система V-Ray. Статические и динамические характе- ристики параллельных программ. Анализ структуры программ. Графовые структу- ры программ на практике. Вопросы и задания. § 9.3. Организационная поддержка пользователя 581 Инфраструктура поддержки работы пользователей. Информационно-аналитический центр по параллельным вычислениям Parallel.ru. Вопросы и задания. Заключение. Параллельные вычисления: интеграция от А до Я 585 Список литературы 588 Интернет-ресурсы 592 Предметный указатель 593 Предметный указатель L L-свойство матрицы 362 А Автокод 31 Автоматическое распараллеливание программ 222 Автономная программная система 323 V-Ray 436 Адрес слова 15 физический 27 Алгоритм: детерминированный 193 линейный 349 недетерминированный 193 параллельный 199 Штрассена 206 Альтернативные многогранники 365 Анализ ошибок: обратный 521 прямой 520 Арифметика: разрядно-параллельная 51 разрядно-последовательная 51 Арифметико-логическое устройство 16 Архитектура: ccNUMA 73 NUMA71 UMA71 Б Байт 15 Барьерная синхронизация 144 Бенчмарк 166 Банк памяти 53 Бит 14 В Вектор: данных 124 граничных значений 462 задержек 462 реализации 462 Величина, заданная на области 313 Вершина: входная 192 выходная 192 Взаимодействие процессов: Put/Get 299 Send/Receive 299 Внутренний код 16 Волновой фронт 406 Время разгона конвейера 125 Выделение стандартных операций 419 Выражение индексное нелинейное 450 Вычисления избыточные 376 Вычислительное ядро 36 Вычислительный кластер 146 Вычисляемые ветвления 449 Г Гиперкуб 69 Гомоморфизм простой 467 Гомоморфная свертка 467 Гомоморфный: образ 467 прообраз 467 594 Предметный указатель Граф: алгоритма 192 влияния 334 вызовов процедур 561 вызовов процедур расширенный 563 зависимостей 333 максимальный 346 минимальный сверху 347 минимальный снизу 346 обратный 347 простой 353 элементарный 354 покрытие 348 информационный 329 использования общей памяти 566 лексикографически правильный 373 направленный 478 направляющий вектор 478 параллельная форма 194 каноническая 194 линейная 195 максимальная 194 обобщенная 195 строгая 194 параметризованный 193 передач управления 327 плоский 488 программы 327 простой канонический вид 371 расширенный 450 регулярный 472 бесконечный 472 базовые векторы 472 базовый многогранник 474 главный регулярный подграф 473 опорные вершины 474 решетчатый 336 сильно связанный 405 системы 84 управления 327 процедурный 569 управляющий 327 эквивалентности 409 элементарный канонический вид 371 Граф-машина 459 Графовая модель программы 326 д Денотационный подход 325 Динамическое порождение процессов 298 Дискретное неравенство Беллмана 466 Дискретное уравнение Беллмана 466 Дистрибутивная решетка 403 Доля последовательных вычислений 87 3 Зависимость 345 data-flow 346 анти 346 истинная 346 по входу 346 по выходу 346 Зависимые точки графа 345 Загруженность: системы 82 устройства 80 Закон: Амдала 1-й 86 Амдала 2-й 87 Густавсона—Барсиса 89 Мура 43 Запятая: плавающая 21 фиксированная 21 Значение неготовое 302 И Иерархия памяти 58 Иллюстративная модель компьютера 38 Информационная структура программы 324 тонкая 324 Информационное ядро 197 Информационные типовые структуры 446 гипотеза 446 История реализации программы 329 Итерация 343 цикла 343 К Каскадный переключатель 66 Классификация: В. Хендлера 103 Д. Скилликорна 110 Л. Шнайдера 107 М. Флинна 97 М. Флинна MIMD 98 М. Флинна MISD 98 М. Флинна SIMD 98 М. Флинна SISD 97 Р. Хокни 100 Т. Фенга 101 Когерентность кэш-памяти 72 Код: внутренний 16 машинный 16 Команда: векторная 48 машинная 16 скалярная 48 Коммуникационный профиль приложений 175 Коммутатор матричный 66 Компилятор 16 Компьютер: ATLAS 53 BBN Butterfly 72 Beowulf-кластеры 147 CDC-6600 53 CDC-7600 53 Cm* 71 Connection Machine 70 Cray C90 116 Cray T3D/T3E 142 Cray-1 57 Hewlett-Packard Superdome 135 IBM 701 51 IBM 704 51 IBM 709 51 ILLIAC IV 54 STRETCH 52 БЭСМ-6 29 M-20 29 MBC-1000M 150 Сетунь 24 Стрела 56 SMP 64 с архитектурой ccNUMA 73 с архитектурой NUMA 71 с архитектурой UMA 71 с общей памятью 63 с распределенной памятью 64 Конвейер: длина 47 команд 53 ступень 47 Концепция неограниченного параллелизма 199 Кортеж система Linda 268 Критическая секция программы 233 Л Лексикографически: неупорядоченные функции 370 упорядоченные функции 370 Лексикографический порядок: в линейном пространстве итераций 344 в программе 344 в пространстве итераций 345 Линейные фрагменты 341 Линейный класс алгоритмов 349 Локальность: вычислений 57 использования данных 57 м Макровершина 405 Макрограф 405 Макродуга 405 Макропараллелизм 374 Массивов: выравнивание 239 распределение 238 Матрица: алгоритма вариационная 505 информационной связности 506 взвешенная 506 инциденций 507 смежностей 507 596 Предметный указатель Машинный нуль 22 Метакомпьютинг 155 Condor 155 GIMPS 156 Globus 156 PACX-MPI 155 SETI@home 156 Микропараллелизм 374 Модель программирования: master/slaves 274 SPMD 275 н Норма 403 О Область 311 Обработка: конвейерная 46 параллельная 44 Обратное выполнение цикла 418 Общая шина 65 Общие данные DVM 242 Операнд 15 Операционная система 17 Операционно-логическая история 328 Операционный подход 325 Операция 15 коллективная 293 произведения областей 311 Опорная область 343 Опорное: гнездо циклов 342 пространство 342 Опорный многогранник 342 Отношение: влияния 335 зависимости 333 п Память 15 адресуемая 26 быстрая 26 виртуальная 28 время доступа 25 конфликты 117 кэш 26 медленная 26 неадресуемая 26 оперативная 26 постоянная 26 проблема когерентности кэш 72 разрядно-параллельная 51 разрядно-последовательная 51 регистровая 26 сверхбыстрая 26 Параллелизм: внутренний 207 координатный 396 массовый 421 скошенный 396 Параллельная форма графа 194 высота 194 каноническая 194 линейная 195 обобщенная 195 строгая 194 ширина 194 ширина яруса 194 ярус 194 Параллельные множества 373 Параллельный алгоритм 199 Передача сообщений: асинхронная 285 синхронная 280 Переменная: координатная 252 локальная 226 неготовая 303 общая 226 размазанная 251 распределенная по сети 250 Перестановка циклов 416 Переупорядочивание операторов 417 Покрытие графа 348 Полукольцо разверток 465 Портабельность программ 33 Порядок: линейный 195 частичный 192 Правило собственных вычислений 237 Принцип близкодействия 488 Проблема отображения 444 Программа 31 иерархическое представление структуры 567 история операционно- логическая 328 история реализации 329 канонизация 448 линейный участок 567 нелинейность устранимая 448 преобразование: специальное 411 треугольное 419 элементарное 413 L-дерево 567 векторизация 123 графовая модель 326 детерминированная 193 исследование: динамическое 571 статическое 341 линейная 340 линейный класс 340 недетерминированная 193 параллельная структура 373 параметр: младший 342 старший 342 портабельность 33 преобразователь 326 простая 353 распознаватель 326 элементарная 354 Производительность: Flops 165 MIPS 164 асимптотическая 86 пиковая 80 реальная 80 Пространство: кортежей 268 итераций 343 переупорядочивание 411 расщепление 418 линейное 343 Процесс сдваивания 200 рекуррентный 203 Процессор 17 матричный 54 с архитектурой VLIW 62 суперскалярный 62 центральный 17 Процессы параллельные FORK/JOIN 226 Прямая подстановка 448 Р Развертка 394 вектор: граничных значений 462 задержек 462 реализации 462 кусочно-линейная 397 направляющий вектор 399 минимальная 464 нулевая 403 обобщенная 394 обобщенная самая строгая 423 основная 395 расщепляющая 395 с ограничениями 463 строгая 394 Раскрутка цикла 131 Распределение цикла 417 Расслоение памяти 52 Рекуррентные соотношения 471 С Свойства метакомпьютера 157 Связи фиктивные 450 Связь: информационная 327 операционная 327 по управлению 327 транспортная 488 шинная 488 Сдваивания рекуррентного процесса 203 Сеть: каскадная перестраиваемая 41 латентность 151 пропускная способность 151 598 Предметный указатель Синхронизация барьерная 144 Система коммутации 65 Система программирования: DVM 235 Linda 268 mpC 248 MPI 275 MPI-2 298 OpenMP 225 НОРМА 309 Т-система 301 Систолическая: система 483 ячейка 483 Систолический массив 482 Скалярное произведение 403 Скашивание цикла 418 Слияние циклов 416 Слово 15 адрес 15 длина 15 содержимое 15 Спецпроцессор 61 Список Тор500 167 Срабатывание оператора 343 Стоимость: операции 80 работы 80 Сумматор 24 т Теневые грани массива 242 Теорема об информационном покрытии 348 Тестирование компьютеров: HINT 176 LINPACK 166 NPB 172 PERFECT Club Benchmarks 171 SPEC 175 STREAM 168 Top500 167 бенчмарк 166 Ливерморские циклы 170 Технологии параллельного программирования 220 Топология: гиперкуба 69 связи процессоров 68 Точка лексикографического максимума 356 У Укладка графа 481 Умножитель 24 Ускорение 83 Устройство 16 ввода/вывода 16 арифметико-логическое 16 загруженность 80 конвейерное 79 время разгона 125 длина 79 ступень 79 оперативное запоминающее 26 простое 79 управления 17 Уточнение внешних переменных 453 Ф Формула Эйлера 499 Фронт: волновой 406 вычислений 406 Функции: базовые 249 лексикографически неупорядоченные 370 лексикографически упорядоченные 370 покрывающие 348 сетевые 254 узловые 249 чистые 302 ц Центральный процессор 17 Цикл: ParDo 374 TrueParDo 578 Циклический профиль: путей 566 фрагмента 569 Эквивалентные: возмущения 521 выражения 408 программы 409 Эффективность 83 Число: двоичные разряды 19 мантисса 22 машинный нуль 22 округление 19 ошибка округления 19 порядок 22 с плавающей запятой 22 с фиксированной запятой 21 э Эквивалентное преобразование программы 409 Я Ядро: вычислительное 36 информационное 197 Язык программирования 31 высокого уровня 31 машинно-независимый 32 низкого уровня 31 однократного присваивания 310 проблемно-ориентированный 31 универсальный 32 |
Программа проведения итогового междисциплинарного экзамена по специальности... Программа составлена проф. Карповым В. С., проф. Токаревым В. Л., доц. Берсеневым Г. Б. и доц. Лебеденко Ю. И. и обсуждена на заседании... |
Мичио каку параллельные миры «софия» 2 0 0 8 Об устройстве мироздания,... К16 Параллельные миры: 06 устройстве мироздания, высших измерениях и будущем Космоса / Перев с англ. — М.: Ооо издательство «София»,... |
||
1. Элементная база микропроцессорных систем Дисциплины, выносимые кафедрой ЭВМ на междисциплинарный экзамен по специальности 230101 «Вычислительные машины, комплексы, системы... |
Методические указания по выполнению лабораторных работ для студентов... Целью лабораторной работы является изучение простейших способов воспроизведения звуковых файлов при помощи использования функции... |
||
Методические указания по выполнению контрольно-курсовой работы для... Цели и задачи выполнения контрольно-курсовой работы |
Разработка численного метода и программного кода для решения трехмерных... М. Численные методы. М.: Наука, 1987; Пейре Р., Тейлор Т. Д. Вычислительные методы в задачах механики жидкости. Л.: Гидрометеоиздат,... |
||
Методические указания по выполнению контрольно-курсовой работы для... Цели и задачи выполнения контрольно-курсовой работы |
Прогнозно-аналитический центр Прогнозно-аналитического центра Академии Управления посвящена вопросам геноцида населения. Авторы преследовали цель показать правду... |
||
Кафедра «Электронных вычислительных машин» методические указания... Методические указания к дипломному проектированию составлены и доц каф ЭВМ лебеденко Ю. И. и обсуждены на заседании кафедры ЭВМ факультета... |
Методические указания по выполнению курсового проекта для студентов... Курсовой проект предназначен для приобретения навыков по схемотехническому проектированию несложных цифровых устройств. Проект выполняется... |
Поиск на сайте Главная страница Литература Доклады Рефераты Курсовая работа Лекции |