Закон Амдала и его следствия

Предположим, что в программе доля операций, которые нужно выполнять последовательно, равна f, где 0<=f<=1 (при этом доля понимается не по статическому числу строк кода, а по числу операций в процессе выполнения). Крайние случаи в значениях f соответствуют полностью параллельным (f=0) и полностью последовательным (f=1) программам. Для того, чтобы оценить, какое ускорение S может быть получено на компьютере из p процессоров при данном значении f, можно воспользоваться законом Амдала [11]:

 

S <= 1/(f+(1-f)/p)

 

Если 9/10 программы исполняется параллельно, а 1/10 по-прежнему последовательно, то ускорения более, чем в 10 раз получить в принципе невозможно вне зависимости от качества реализации параллельной части кода и числа используемых процессоров (ясно, что 10 получается только в том случае, когда время исполнения параллельной части равно 0).

Посмотрим на проблему с другой стороны: а какую же часть кода надо ускорить (а значит и предварительно исследовать), чтобы получить заданное ускорение? Ответ можно найти в следствии из закона Амдала: для того чтобы ускорить выполнение программы в q раз необходимо ускорить не менее, чем в q раз не менее, чем (1-1/ q)-ю часть программы. Следовательно, если есть желание ускорить программу в 100 раз по сравнению с ее последовательным вариантом, то необходимо получить не меньшее ускорение не менее, чем на 99% кода, что почти всегда составляет значительную часть программы!

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

Словом, заставить параллельную вычислительную систему или супер-ЭВМ работать с максимальной эффективность на конкретной программе - задача не из простых, поскольку необходимо тщательное согласование структуры программ и алгоритмов с особенностями архитектуры параллельных вычислительных систем.

 

Наиболее известные современные многопроцессорные компьютеры

Согласно данным [11], в настоящее время к наиболее известным мультипроцессорным системам относятся нижеследующие.

 

IBM RS/6000 SP

Производитель	International Business Machines (IBM), подразделение RS/6000.
Класс архитектуры	Масштабируемая массивно-параллельная вычислительная система (MPP).
Узлы	Узлы имеют архитектуру рабочих станций RS/6000. Существуют несколько типов SP-узлов, которые комплектуются различными процессорами: PowerPC 604e/332MHz, POWER3/200 и 222 MHz (более ранние системы комплектовались процессорами POWER2). High-узлы на базе POWER3 включают до 8 процессоров и до 16 GB памяти.
Масштабируемость	До 512 узлов. Возможно совмещение узлов различых типов. Узлы устанавливаются в стойки (до 16 узлов в каждой).
Коммутатор	Узлы связаны между собой высокопроизводительных коммутатором (IBM high-performance switch), который имеет многостадийную структуру и работает с коммутацией пакетов.
Cистемное ПО	OC AIX (устанавливается на каждом узле), система пакетной обработки LoadLeveler, параллельная файловая система GPFS, параллельная СУБД INFORMIX-OnLine XPS. Параллельные приложения исполняются под управлением Parallel Operating Environment (POE).
Средства программирования	Оптимизированная реализация интерфейса MPI, библиотеки параллельных математических подпрограмм - ESSL, OSL.

 

 

HP 9000 (Exemplar)

Производитель	Hewlett-Packard, подразделение высокопроизводительных систем.
Класс	Многопроцессорные сервера с общей памятью (SMP).
Предшественники	SMP/NUMA-системы Convex SPP-1200, SPP-1600, SPP-2000.
Модификации	В настоящее время доступны несколько "классов" систем семейства HP 9000: сервера начального уровня (D,K-class), среднего уровня (N-class) и наиболее мощные системы (V-class).
Процессоры	64-битные процессоры c архитектурой PA-RISC 2.0 (PA-8200, PA-8500).
Число процессоров	N-class - до 8 процессоров. V-class - до 32 процессоров. В дальнейшем ожидается увеличение числа процессоров до 64, а затем до 128.
Масштабируемость	SCA-конфигурации (Scalable Computing Architecture) - до 4 узлов V-class, т.е. до 128 процессоров.
Системное ПО	Устанавливается операционная система HP-UX (совместима на уровне двоичного кода с ОС SPP-UX компьютеров Convex SPP).
Средства программирования	HP MPI - реализация MPI 1.2, оптимизированная к архитектуре Exemplar. Распараллеливающие компиляторы Fortran/C, математическая библиотека HP MLIB. CXperf - с редство анализа производительности программ.

 

 

Cray T3E

Производитель	Silicon Graphics
Класс архитектуры	Масштабируемая массивно-параллельная система, состоит из процессорных элементов (PE).
Предшественники	Cray T3D
Модификации	В настоящее время существуют две модификации: T3E-900 и T3E-1200.
Процессорный элемент	PE состоит из процессора, блока памяти и устройства сопряжения с сетью. Используются процессоры Alpha 21164 (EV5) с тактовой частотой 450 MHz (T3E-900) и 600 MHz (T3E-1000), пиковая производительность которых составляет 900 и 1200 MFLOP/sec соответственно. Процессорный элемент располагает своей локальной памятью (DRAM) объемом от 256MB до 2GB.
Число процессоров	Системы T3E масштабируются до 2048 PE.
Коммутатор	Процессорные элементы связаны высокопроизводительной сетью с топологией трехмерного тора и двунаправленными каналами. Скорость обменов по сети достигает 480MB/sec в каждом направлении.
Системное ПО	Используется операционная система UNICOS/mk.
Средства программирования	Поддерживается явное параллельное программирование c помощью пакета Message Passing Toolkit (MPT) - реализации интерфейсов передачи сообщений MPI, MPI-2 и PVM, библиотека Shmem. Для Фортран-программ возможно также неявное распараллеливание в моделях CRAFT и HPF. Среда разработки включает также набор визуальных средств для анализа и отладки параллельных программ.

 

 

Cray T90

Производитель	Silicon Graphics, Cray Research.
Класс архитектуры	Многопроцессорная векторная система (несколько векторных процессоров работают на общей памяти).
Предшественники	CRAY Y-MP C90, CRAY X-MP.
Модели	Серия T90 включает модели T94, T916 и T932.
Процессор	Системы серии T90 базируются на векторно-конвейерном процессоре Cray Research с пиковой производительностью 2GFlop/s.
Число процессоров	Система T932 может включать до 32 векторных процессоров (до 4-х в модели T94, до 16 модели T916), обеспечивая пиковую производительность более 60GFlop/s.
Масштабируемость	Возможно объединение нескольких T90 в MPP-системы.
Память	Система T932 содержит от 1GB до 8GB (до 1 GB в модели T94 и до 4GB в модели T916) оперативной памяти и обеспечивает скорость обменов с памятью до 800MB/sec.
Системное ПО	Используется операционная система UNICOS.

 

Cray SV1

Производитель	Silicon Graphics
Класс архитектуры	Масштабируемый векторный суперкомпьютер.
Процессор	Используются 8-конвейерные векторные процессоры MSP (Multi-Streaming Processor) с пиковой производительностью 4.8 GFLOP/sec; каждый MSP может быть подразделен на 4 стандартных 2-конвейерных процессора с пиковой производительностью 1.2 GFLOP/sec. Тактовая частота процессоров - 250MHz.
Число процессоров	Процессоры объединяются в SMP-узлы, каждый из которых может содержать 6 MSP и 8 стандартных процессоров. Система (кластер) может содержать до 32 таких узлов.
Память	SMP-узел может содержать от 2 до 16GB памяти. Система может содержать до 1TB памяти. Вся память глобально адресуема (архитектура DSM).
Системное ПО	Используется операционная система UNICOS.
Средства программирования	Поставляется векторизующий и распараллеливающий компилятор CF90. Поддерживается также явное параллельное программирование с использованием интерфейсов MPI, OpenMP или Shmem.

 

 

 

 

Cray Origin2000

Производитель	Silicon Graphics
Класс архитектуры	Модульная система с общей памятью (cc-NUMA).
Процессор	64-разрядные RISC-процессоры MIPS R10000, R12000/300MHz
Модуль	Основной компонент системы - модуль Origin, включающий от 2 до 8 процессоров MIPS R10000 и до 16GB оперативной памяти.
Масштабируемость	Поставляются системы Origin2000, содержащие до 256 процессоров (т.е. до 512 модулей). Вся память системы (до 256GB) глобально адресуема, аппаратно поддерживается когерентность кэшей.
Коммутатор	Модули системы соединены с помощью сети CrayLink, построенной на маршрутизаторах MetaRouter.
Системное ПО	Используется операционная система SGI IRIX.
Средства программирования	Поставляется распараллеливающий компилятор Cray Fortran 90. Поддерживается стандарт OpenMP.

 

 

Onyx2 InfiniteReality2

Производитель	Silicon Graphics
Класс архитектуры	Многопроцессорная система визуализации; по аппаратной архитектуре очень похожа на Origin2000.
Число процессоров	Система может включать до 128 процессоров MIPS R10000.
Визуализация	Графические возможности системы обеспечивают специальные устройства трех типов: геометрические (векторные) процессоры, растровые процессоры, генераторы аналоговых сигналов. Система может быть оборудована 16 независимыми каналами графического вывода (visualization pipelines). На аппаратном уровне поддерживается графический интерфейс OpenGL.
Системное ПО	Используется операционная система SGI IRIX.

 

Sun HPC 10000 (StarFire)

Производитель	Sun Microsystems, серия Sun HPC.
Класс архитектуры	Многопроцессорный SMP-сервер.
Процессор	UltraSPARC II/336MHz
Число процессоров	Система StarFire объединяет от 16 до 64 процессоров.
Память	Система включает от 2GB до 64GB памяти.
Системное ПО	ОС Solaris, ПО распределения ресурсов Load Sharing Facility (LSF).
Средства разработки	Поставляется пакет поддержки параллельных приложений Sun HPC 2.0, включающий такие средства как HPF, MPI, PVM, PFS (параллельная файловая система), Prism (визуальная среда разработки), S^3L (библиотека математических подпрограмм), и др.

 

Sun Fire 15K

Производитель	Sun Microsystems.
Класс архитектуры	Многопроцессорный SMP-сервер.
Процессор	UltraSPARC III/900MHz
Число процессоров	Система Sun Fire 15K объединяет до 106 процессоров.
Память	Система включает до 576GB памяти.
Системное ПО	ОС Solaris 8.

 

NEC SX-5

Производитель	NEC, серия SX.
Класс архитектуры	Параллельный векторный суперкомпьютер (PVP).
Предшественники	NEC SX-4.
Узел	Каждый узел системы является векторно-конвейерным SMP-суперкомпьютером, объединяющим до 16 индивидуальных векторных процессоров (каждый с пиковой векторной производительностью 8 Gflop/s и скалярной производительностью 500 MFlop/s).
Память	Объем памяти каждого узла - до 128GB, производительность обменов с памятью достигает 1TB/sec.
Масштабируемость	Система может включать до 32 узлов, обеспечивая совокупную пиковую производительность до 4 TFlop/s.
Коммутатор	Для связи узлов используется высокоскоростной коммутатор (IXS Internode Crossbar Switch).
Системное ПО	Используется операционная система SUPER-UX.
Средства программирования	поставляются компилятор языка HPF, реализация интерфейса MPI, компиляторы Фортран 77/90 с автоматической векторизацией и поддержкой OpenMP 1.1, а также интегрированная среда разработки и оптимизации PSUITE.

NEC SX-6

Производитель	NEC, серия SX.
Класс архитектуры	Параллельный векторный суперкомпьютер (PVP).
Предшественники	NEC SX-5.
Узел	Каждый узел системы является векторно-конвейерным SMP-суперкомпьютером, объединяющим от 2 до 8 индивидуальных векторных процессоров (каждый с пиковой векторной производительностью 8 Gflop/s и скалярной производительностью 500 MFlop/s).
Память	Объем памяти каждого узла - до 64GB, производительность обменов с памятью достигает 1TB/sec.
Масштабируемость	Система может включать до 128 узлов, обеспечивая совокупную пиковую производительность до 8 TFlop/s.
Коммутатор	Для связи узлов используется высокоскоростной коммутатор (IXS Internode Crossbar Switch).
Системное ПО	Используется операционная система SUPER-UX с улучшенной поддержкой SSI (Single System Image).
Средства программирования	поставляются компилятор языка HPF 2.0, реализация интерфейса MPI, компиляторы Фортран 77/90 с автоматической векторизацией, интегрированная среда разработки и оптимизации PSUITE, поддерживается OpenMP 1.1 (в конце 2002 года предполагается поддержка OpenMP 2.0).

Fujitsu VPP

Производитель	Fujitsu
Класс архитектуры	Параллельный векторный суперкомпьютер (PVP).
Модификации	VPP300, VPP700, VPP5000
Процессорный элемент	Каждый процессорный элемент (PE) системы VPP700E состоит скалярного устройства (SU), векторного устройства (VU), блока памяти и устройства сопряжения. Для VPP700: VU состоит из 7 конвейеров и обеспечивает пиковую производительность до 2.4 GFLOP/sec. Объем памяти - до 2GB. Для VPP5000: VU состоит из 4 конвейеров, пиковая производительность - 9.6 GFLOP/sec. Объем памяти - до 16GB.
Масштабируемость	Для VPP700: cистема может включать от 8 до 256 PE, суммарная пиковая производительность до 14.4 GFLOP/sec Для VPP5000: до 512 PE, суммарная пиковая производительность до 4.9 TFLOP/sec.
Коммутатор	Процессорные элементы связаны коммутатором (crossbar network), который производить двухсторонние обмены, не прерывая вычислений. Пропускная способность каналов коммутатора: для VPP700 - 615MB/sec, для VPP5000 - 1.6GB/sec.
Системное ПО	Используется операционная система UXP/V, основанная на UNIX System VR4.
Средства программирования	Среди средств разработки поставляются: распараллеливающий и векторизующий компилятор Fortran90/VPP, оптимизированная для VPP библиотека математических подпрограмм SSLII/VPP, библиотеки передачи сообшений MPI-2 и PVM 3.3.

 

 

AlphaServer

Производитель	Compaq (Digital).
Класс архитектуры.	AlphaServer GS/ES - высокопроизводительный SMP-сервер, AlphaServer SC - массивно-параллельная система, AlphaServer HPC - кластерные системы.
Модификации	GS320, GS160, HPC320, HPC160, GS140, GS60, ES40, DS20 и др.
Процессор	Alpha 21264, 21264A (тактовая частота до 731 MHz в новых моделях)
Число процессоров	до 32 (модель GS320)
Память	до 256 GB (модель GS320)
Масштабируемость	Системы HPC320 включают до 4-х узлов AlphaServer ES40, т.е. до 16 процессоров. Системы AlphaServer SC могут объединять до 128 узлов AlphaServer ES40, т.е. до 512 процессоров. Также Compaq предлагает разнообразные кластерные решения на базе своих серверов.
Системное ПО	На платформе AlphaServer поддерживаются операционные системы Tru64 UNIX (это новое имя Digital UNIX), OpenVMS и Linux. Поставляется ПО кластеризации TruCluster Software.
Средства программирования	Поддерживается параллельное программирование в стандартах OpenMP и MPI.

 

 

 

RM600 E

Производитель	Siemens Computer Systems (SNI), серия RM Servers.
Класс архитектуры	Многопроцессорная система с общей памятью (cc-NUMA).
Модификации	E60, E20
Процессор	Используются процессоры MIPS R10000 (200MHz).
Число процессоров	Процессорные платы с SMP-архитектурой объединяют до 4-х процессоров. Система включает в общей сложности до 24 процессоров в модели E60 и до 8 в модели E20.
Память	Общий объем оперативной памяти систем E60 - до 4GB, а систем E20 - до 2GB. Архитектура памяти системы - NUMA.
Масштабируемость	Несколько систем RM600 E могут объединяться в кластерную (MPP) систему - Reliant Cluster Server.
Системное ПО	Устанавливается операционная система Reliant UNIX.

 

 

QM-1

Производитель	Quadrics Supercomputers World Ltd. (QSW).
Класс архитектуры	Кластерная система
Процессор	UltraSPARC II/250 или 300 MHz c пиковой производительностью 500 MFLOP/sec (600 MFLOP/sec). На каждом процессоре находятся кэши данных и команд первого уровня по 16K и внешняя кэш-память объемом 1 или 2 МB.
Узел	Каждый узел системы содержит от 1 до 4 процессоров над общей памятью, внешние устройства и коммуникационный процессор (Elan3), осуществляющий доступ в память других узлов.
Масштабируемость	В максимальной конфигурации может быть более 4000 узлов.
Память	Максимальный объем памяти для узла составляет 2GB. Скорость обменов с памятью внутри узла составляет 1.78 GB/sec.
Сеть	Заявленная скорость обменов с другими узлами составляет 250 МB/sec одновременно в двух направлениях, а латентность сети - 2 мкс.
Средства программирования	Реализованы средства параллельного программирования HPF, PVM, PARMACS, NX/2 и MPI.

 

 

NUMA-Q 2000

Производитель	IBM (ранее - Sequent)
Класс архитектуры	Многопроцессорная система с общей памятью (cc-NUMA) Используется для организации сложных информационных систем.
Модификации	Model E410/E330/E320/E300/E200
Процессоры	Intel Pentium III Xeon (700 MHz в модели E410)
Узел	от 4 до 64 процессоров, до 64 GB оперативной памяти; узел состоит из базовых плат по 4 процессора (quads), соединенных между собой коммутатором IQ-Link.
Масштабируемость	Возможна организация кластеров, включающих до 4 узлов
Системное ПО	Используется операционная система DYNIX/ptx - версия UNIX от Sequent. Внутри одной системы могут одновременно исполняться UNIX и Windows NT.

 

 

AViiON

Производитель	Data General (подразделение EMC)
Класс архитектуры	Многопроцессорная система с общей памятью (cc-NUMA). По аппаратной архитектуре похожа на сервера Sequent NUMA-Q. Используется для организации сложных информационных систем.
Модификации	AV25000, AV20000, AV10000 (корпоративные сервера)
Процессоры	Pentium II Xeon, Pentium III Xeon
Узел	От 4 до 64 процессоров, до 64 GB оперативной памяти. Сервер включает до 16 блоков (SBB, Scalable Building Block) на основе материнских плат SHV от Intel, в каждом из которых по 4 процессора и до 4GB памяти.
Масштабируемость	Возможна организация 2-серверных кластеров QuickClusters.
Системное ПО	Используются ОС DG/UX (версия UNIX от Data General) и Windows NT.

 

 

WorldMark

Производитель	NCR.
Класс архитектуры	Массивно-параллельная система на базе SMP-узлов. Используется для построения параллельных СУБД, масштабируемых систем Data Warehousing.
Модификации	WorldMark 5200/5150/5100M/5100C/5100S/4800/4700.
Процессоры	Intel Pentium II Xeon, Pentium Pro, Pentium.
Узел	Для WorldMark 5100M в качестве узла используется SMP-сервер 5100S - до 32 процессоров, до 4 GB оперативной памяти.
Масштабируемость	До 128 узлов, 4096 процессоров (для WorldMark 5100M).
Коммуникационная сеть	Узлы объединяются c помощью сети BYNET V2 (120 MB/sec).
Системное ПО	Операционная система NCR UNIX SVR4 MP-RAS. Параллельные СУБД: NCR Teradata, Oracle Parallel Server и др.

 

ВОПРОСЫ ДЛЯ САМОПРОВЕРКИ

1. В чем отличие числовой и нечисловой обработки данных?

2. Перечислите ограничения фон-неймановской архитектуры.

3. Поясните суть параллельной обработки данных.

4. Поясните конвейерную обработку данных.

5. Что такое «время разгона» конвейера?

6. Поясните суть организации векторных конвейеров.

7. Проведите классификацию архитектур вычислительных систем.

8. Расскажите о мультипроцессорных системах с общей памятью.

9. Расскажите о мультипроцессорных системах с локальной памятью.

10. Перечислите базовые архитектуры суперкомпьютеров.

11. Расскажите об архитектуре современных векторных суперкомпьютеров.

12. Что такое ассоциативная память и ассоциативный процессор?

13. Изложите концепцию вычислительных систем с управлением потоком данных.

14. Поясните закон Амдала и его следствия.

Глава 3.
Введение в теорию
массового обслуживания
и управления ресурсами
вычислительных систем