Воеводину за идеи и критику,
Александру Наумову и Антону Коржу за предоставленный материал и консультации,
Виктору Дацюку, Павлу Костенецкому, Алексею Лацису и Юрию Хребтову за важные замечания.
Вадиму Кузнецову (dikbsd) за неоценимую помощь в конвертации книги в электронный формат.
Глава 1. Что же такое «супер»?
Общие понятия о параллельной обработке и параллельных программах
Все современные суперкомпьютеры используют параллельную обработку данных. С самого начала компьютерной эры именно этот путь был и остаётся наиболее важным для достижения высокой производительности. Сейчас даже самый простой настольный компьютер если не многоядерный, то уж почти наверняка с технологией simultaneous multithreading (например, HyperThreading от Intel или AMD SMT), позволяющей работать двум (иногда более) программным потокам одновременно. Даже мобильные телефоны и фотоаппараты становятся параллельными и многоядерными.
Принцип параллельной обработки данных прост: если две или более операции независимы (т. е. результаты их выполнения не влияют на входные данные друг друга), то эти операции можно выполнить одновременно, т. е. параллельно. В аппаратуре традиционно есть два варианта воплощения этого принципа – параллелизм и конвейеризация.
Параллелизм – параллельное выполнение машинных команд разными устройствами. Например, команды x=a+b и y=b*c, где a, b и с – регистры, процессор может выполнить независимо, если он имеет раздельные устройства сложения и умножения (см. рис. 1). Этот принцип воплощён в большинстве современных процессоров.
Конвейеризация – разделение команд на этапы, каждый из которых выполняется быстро отдельным элементом аппаратуры, и выполнение этих этапов происходит по принципу конвейера: друг за другом. Таким образом, одновременно может выполняться несколько команд на разных стадиях конвейера. Наиболее часто этот принцип используется в векторизации – выполнении однотипной операции над векторами, т. е. массивами данных, расположенными в памяти регулярно (см. рис. 2).
Рис. 1: Параллельное выполнение
Рис. 2: Векторизация + конвейер
Чаще всего элементы вектора расположены друг за другом. Типичный пример – сложение векторов. Так как операция, выполняющаяся над векторами, одна и та же, то её разбивают на фазы – ступени конвейера. Например, загрузка элементов из памяти, нормализация мантисс, сложение, коррекция, запись в память. После выполнения первой ступени над первым элементом вектора эту стадию можно сразу же выполнить над вторым элементом, не дожидаясь завершения всей операции над первым. После завершения каждой ступени над одним элементом можно выполнить её над следующим. Таким образом, если самая медленная ступень конвейера выполняется за К тактов, а все ступени – за S тактов, то вектор из N элементов обработается за K*(N–1)+S.
Первый элемент обработается за положенные S тактов (это называется
