Параллелизм на уровне команд

Параллелизм на уровне команд (англ. Instruction-level parallelism - ILP) — является мерой того, какое множество операций в компьютерной программе может выполняться одновременно. Потенциальное совмещение выполнения команд называется "параллелизмом на уровне команд".

Описание

Есть два подхода к параллелизму на уровне команд:

• аппаратные средства
• программное обеспечение

Уровень аппаратного обеспечения работает на динамическом параллелизме, тогда как, уровень программного обеспечения работает на статическом параллелизме. Современные высокопроизводительные процессоры x86 (Intel Pentium 4, Intel Core) работают на динамической последовательности параллельного выполнения (Внеочередное исполнение команд). Статический параллелизм применялся в процессорах Itanium (однако в Itanium 2 применяется гибридный подход).

Рассмотрим следующую программу:

1. e = a + b
2. f = c + d
3. m = e * f

Операция 3 зависит от результатов 1 и 2, поэтому она не может быть рассчитана, пока обе из них не будут завершены. Однако операции 1 и 2 не зависят от любой другой операции, так что они могут быть вычислены одновременно. Если предположить, что каждая операция может быть завершена в одну единицу времени, то эти три инструкции могут быть завершены в общей сложности за две единицы времени, давая ILP 3/2.

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

Сколько ILP существует в программах - сильно зависит от области применения программы. В некоторых областях, таких как графики и научные вычисления, число может быть очень большим. Тем не менее, рабочие нагрузки, такие как криптография, могут проявлять гораздо меньше параллелизма.

Микроархитектурные методы для обеспечения ILP:

• Вычислительный конвейер, где выполнение нескольких инструкций может частично перекрываться.
• Суперскалярное выполнение, VLIW и тесно связанная с ними концепция микропроцессорной архитектуры с явным параллелизмом команд, в которой несколько функциональных блоков используются для выполнения нескольких команд параллельно
• Внеочередное исполнение, где инструкции выполняются в любом порядке, который не нарушает зависимости данных. Обратите внимание, что этот метод не зависит ни от конвейера, ни от суперскаляра. Текущая реализация внеочередного исполнения динамично (то есть, в то время как программа выполняется и без всякой помощи со стороны компилятора) извлекает ILP от обычных программ. В качестве альтернативы можно извлечь этот параллелизм во время компиляции и как-то передать эту информацию к аппаратному обеспечению. Из-за сложности техники пересчета внеочередного исполнения, промышленность пересмотрела набор команд, которые явно кодируют несколько независимых операций в инструкции.
• Переименование регистров, которое ссылается на метод, используемый, чтобы избежать ненужной сериализации операций, произведенных программой, которые налагают повторное использование регистров по этим операциям, используется для внеочередного исполнения.
• Спекулятивное выполнение, которое позволяет выполнению полных инструкций или частей инструкций убедиться, следует ли этому выполнению состояться. Часто используемой формой спекулятивного исполнения является предположение управления потоком, где инструкции пропускают управление потоком инструкций (например, переход) и выполняются до того как определится цель потока управления инструкций. Несколько другие формы спекулятивного исполнения были предложены и используются в том числе для спекулятивного исполнения, обусловлены прогнозированием значения, прогнозирования зависимости памяти и прогнозирования латентности кэша.
• Предсказание переходов, который используется, чтобы избежать приостановки контроля зависимостей, которые необходимо решить. Предсказатель переходов используется со спекулятивным исполнением.

Потоковые архитектуры представляют собой другой класс архитектур, где ILP явно указаны, см., например, архитектуру TRIPS.

Реализации

Ранние реализации ILP, в таких мейнфреймах как IBM System/360 Model 91, использовали методы ILP, чтобы преодолеть ограничения, налагаемые относительно небольшим регистровым файлом.

В микропроцессорах различные формы параллелизма на уровне инструкций стали применяться с конца 1980-х. В качестве примера первых суперскалярных процессоров можно привести Intel 960CA (1989 год), IBM Power RS/6000 (1990 год), DEC Alpha 21064 (1992 год). Внеочередное исполнение команд и переименование регистров в микропроцессорах впервые было реализовано в IBM POWER1 (1990 г.).

Первым IA-32-процессором с конвейером стал Intel 80486 (1989 г.); первым суперскалярным IA-32-процессором стал Intel Pentium (1993 г); первый IA-32-процессор с внеочередным исполнением команд и переименованием регистров - Intel Pentium Pro (1995 г.),

В период с 1999 по 2005 год компании AMD и Intel вели активную конкурентную борьбу по выпуску все более и более производительных микропроцессоров для массового потребительского и серверного рынков. В процессорах, выпущенных за этот период, обеими компаниями активно совершенствовались техники эксплуатации параллелизма на уровне команд. Например, в архитектуре NetBurst компания Intel наращивала стадии вычислительного конвейера, доведя их число в Pentium 4 Prescott до 31. Обе компании повышали тактовую частоту процессоров (т.н. "гонка гигагерцев"), уменьшали техпроцесс, чтобы поместить еще больше транзисторов на подложке процессора с целью использовать их для еще большего повышения эффективности работы суперскалярных конвейеров.

К концу 2005 года стало ясно, что все эти способы и методы себя исчерпали. При неизменных темпах увеличения количества транзисторов производительность самих процессоров повышалась незначительно, но при этом росло энергопотребление процессоров и их тепловыделение, приблизившись к ограничениям недорогих систем теплоотвода (power ceiling, power wall).

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

См. также

• Зависимость данных

Литература

• David A. Patterson, John L. Hennessy. [books.google.com/books?id=v3-1hVwHnHwC Computer Architecture: A Quantitative Approach, 5th Edition]. — Morgan Kaufmann, 2011. — 856 p. — ISBN 012383872X. (англ.) - Глава 3, стр.148-247

• под ред. David Padua. [books.google.com/books?isbn=0387098445 Encyclopedia of Parallel Computing]. — Springer, 2012. — 2366 p. — ISBN 0387098445. (англ.) - стр.935

• David Harris, Sarah Harris. [books.google.com/books?id=-DG18Nf7jLcC Digital Design and Computer Architecture, 2nd Ed]. — Morgan Kaufmann, 2012. — 712 p. — ISBN 0123944244. (англ.) - стр.444-452

• David A. Patterson, John L. Hennessy. [books.google.com/books?id=EVhgAAAAQBAJ Computer Organization and Design: The Hardware/Software Interface, 5th Edition]. — Morgan Kaufmann, 2013. — 800 p. — ISBN 0124077269. (англ.) - Глава 4.10, стр.332-344

Ссылки

• [www.edn.com/design/systems-design/4368983/Future-of-computing--Part-3-The-ILP-Wall-and-pipelines Future of computing - Part 3: The ILP Wall and pipelines], EDN, 2012 (англ.)
• [habrahabr.ru/post/145432/ Герб Саттер. Бесплатного супа больше не будет // Herb Sutter. The Free Lunch Is Over: A Fundamental Turn Toward Concurrency in Software] (рус.)

Отрывок, характеризующий Параллелизм на уровне команд

Движение народов начинает укладываться в свои берега. Волны большого движения отхлынули, и на затихшем море образуются круги, по которым носятся дипломаты, воображая, что именно они производят затишье движения.
Но затихшее море вдруг поднимается. Дипломатам кажется, что они, их несогласия, причиной этого нового напора сил; они ждут войны между своими государями; положение им кажется неразрешимым. Но волна, подъем которой они чувствуют, несется не оттуда, откуда они ждут ее. Поднимается та же волна, с той же исходной точки движения – Парижа. Совершается последний отплеск движения с запада; отплеск, который должен разрешить кажущиеся неразрешимыми дипломатические затруднения и положить конец воинственному движению этого периода.
Человек, опустошивший Францию, один, без заговора, без солдат, приходит во Францию. Каждый сторож может взять его; но, по странной случайности, никто не только не берет, но все с восторгом встречают того человека, которого проклинали день тому назад и будут проклинать через месяц.
Человек этот нужен еще для оправдания последнего совокупного действия.
Действие совершено. Последняя роль сыграна. Актеру велено раздеться и смыть сурьму и румяны: он больше не понадобится.
И проходят несколько лет в том, что этот человек, в одиночестве на своем острове, играет сам перед собой жалкую комедию, мелочно интригует и лжет, оправдывая свои деяния, когда оправдание это уже не нужно, и показывает всему миру, что такое было то, что люди принимали за силу, когда невидимая рука водила им.
Распорядитель, окончив драму и раздев актера, показал его нам.
– Смотрите, чему вы верили! Вот он! Видите ли вы теперь, что не он, а Я двигал вас?
Но, ослепленные силой движения, люди долго не понимали этого.
Еще большую последовательность и необходимость представляет жизнь Александра I, того лица, которое стояло во главе противодвижения с востока на запад.
Что нужно для того человека, который бы, заслоняя других, стоял во главе этого движения с востока на запад?
Нужно чувство справедливости, участие к делам Европы, но отдаленное, не затемненное мелочными интересами; нужно преобладание высоты нравственной над сотоварищами – государями того времени; нужна кроткая и привлекательная личность; нужно личное оскорбление против Наполеона. И все это есть в Александре I; все это подготовлено бесчисленными так называемыми случайностями всей его прошедшей жизни: и воспитанием, и либеральными начинаниями, и окружающими советниками, и Аустерлицем, и Тильзитом, и Эрфуртом.
Во время народной войны лицо это бездействует, так как оно не нужно. Но как скоро является необходимость общей европейской войны, лицо это в данный момент является на свое место и, соединяя европейские народы, ведет их к цели.
Цель достигнута. После последней войны 1815 года Александр находится на вершине возможной человеческой власти. Как же он употребляет ее?
Александр I, умиротворитель Европы, человек, с молодых лет стремившийся только к благу своих народов, первый зачинщик либеральных нововведений в своем отечестве, теперь, когда, кажется, он владеет наибольшей властью и потому возможностью сделать благо своих народов, в то время как Наполеон в изгнании делает детские и лживые планы о том, как бы он осчастливил человечество, если бы имел власть, Александр I, исполнив свое призвание и почуяв на себе руку божию, вдруг признает ничтожность этой мнимой власти, отворачивается от нее, передает ее в руки презираемых им и презренных людей и говорит только:
– «Не нам, не нам, а имени твоему!» Я человек тоже, как и вы; оставьте меня жить, как человека, и думать о своей душе и о боге.

Как солнце и каждый атом эфира есть шар, законченный в самом себе и вместе с тем только атом недоступного человеку по огромности целого, – так и каждая личность носит в самой себе свои цели и между тем носит их для того, чтобы служить недоступным человеку целям общим.
Пчела, сидевшая на цветке, ужалила ребенка. И ребенок боится пчел и говорит, что цель пчелы состоит в том, чтобы жалить людей. Поэт любуется пчелой, впивающейся в чашечку цветка, и говорит, цель пчелы состоит во впивании в себя аромата цветов. Пчеловод, замечая, что пчела собирает цветочную пыль к приносит ее в улей, говорит, что цель пчелы состоит в собирании меда. Другой пчеловод, ближе изучив жизнь роя, говорит, что пчела собирает пыль для выкармливанья молодых пчел и выведения матки, что цель ее состоит в продолжении рода. Ботаник замечает, что, перелетая с пылью двудомного цветка на пестик, пчела оплодотворяет его, и ботаник в этом видит цель пчелы. Другой, наблюдая переселение растений, видит, что пчела содействует этому переселению, и этот новый наблюдатель может сказать, что в этом состоит цель пчелы. Но конечная цель пчелы не исчерпывается ни тою, ни другой, ни третьей целью, которые в состоянии открыть ум человеческий. Чем выше поднимается ум человеческий в открытии этих целей, тем очевиднее для него недоступность конечной цели.
Человеку доступно только наблюдение над соответственностью жизни пчелы с другими явлениями жизни. То же с целями исторических лиц и народов.


Свадьба Наташи, вышедшей в 13 м году за Безухова, было последнее радостное событие в старой семье Ростовых. В тот же год граф Илья Андреевич умер, и, как это всегда бывает, со смертью его распалась старая семья.
События последнего года: пожар Москвы и бегство из нее, смерть князя Андрея и отчаяние Наташи, смерть Пети, горе графини – все это, как удар за ударом, падало на голову старого графа. Он, казалось, не понимал и чувствовал себя не в силах понять значение всех этих событий и, нравственно согнув свою старую голову, как будто ожидал и просил новых ударов, которые бы его покончили. Он казался то испуганным и растерянным, то неестественно оживленным и предприимчивым.
Свадьба Наташи на время заняла его своей внешней стороной. Он заказывал обеды, ужины и, видимо, хотел казаться веселым; но веселье его не сообщалось, как прежде, а, напротив, возбуждало сострадание в людях, знавших и любивших его.
После отъезда Пьера с женой он затих и стал жаловаться на тоску. Через несколько дней он заболел и слег в постель. С первых дней его болезни, несмотря на утешения докторов, он понял, что ему не вставать. Графиня, не раздеваясь, две недели провела в кресле у его изголовья. Всякий раз, как она давала ему лекарство, он, всхлипывая, молча целовал ее руку. В последний день он, рыдая, просил прощения у жены и заочно у сына за разорение именья – главную вину, которую он за собой чувствовал. Причастившись и особоровавшись, он тихо умер, и на другой день толпа знакомых, приехавших отдать последний долг покойнику, наполняла наемную квартиру Ростовых. Все эти знакомые, столько раз обедавшие и танцевавшие у него, столько раз смеявшиеся над ним, теперь все с одинаковым чувством внутреннего упрека и умиления, как бы оправдываясь перед кем то, говорили: «Да, там как бы то ни было, а прекрасжейший был человек. Таких людей нынче уж не встретишь… А у кого ж нет своих слабостей?..»
Именно в то время, когда дела графа так запутались, что нельзя было себе представить, чем это все кончится, если продолжится еще год, он неожиданно умер.
Николай был с русскими войсками в Париже, когда к нему пришло известие о смерти отца. Он тотчас же подал в отставку и, не дожидаясь ее, взял отпуск и приехал в Москву. Положение денежных дел через месяц после смерти графа совершенно обозначилось, удивив всех громадностию суммы разных мелких долгов, существования которых никто и не подозревал. Долгов было вдвое больше, чем имения.
Родные и друзья советовали Николаю отказаться от наследства. Но Николай в отказе от наследства видел выражение укора священной для него памяти отца и потому не хотел слышать об отказе и принял наследство с обязательством уплаты долгов.
Кредиторы, так долго молчавшие, будучи связаны при жизни графа тем неопределенным, но могучим влиянием, которое имела на них его распущенная доброта, вдруг все подали ко взысканию. Явилось, как это всегда бывает, соревнование – кто прежде получит, – и те самые люди, которые, как Митенька и другие, имели безденежные векселя – подарки, явились теперь самыми требовательными кредиторами. Николаю не давали ни срока, ни отдыха, и те, которые, по видимому, жалели старика, бывшего виновником их потери (если были потери), теперь безжалостно накинулись на очевидно невинного перед ними молодого наследника, добровольно взявшего на себя уплату.
Ни один из предполагаемых Николаем оборотов не удался; имение с молотка было продано за полцены, а половина долгов оставалась все таки не уплаченною. Николай взял предложенные ему зятем Безуховым тридцать тысяч для уплаты той части долгов, которые он признавал за денежные, настоящие долги. А чтобы за оставшиеся долги не быть посаженным в яму, чем ему угрожали кредиторы, он снова поступил на службу.
Ехать в армию, где он был на первой вакансии полкового командира, нельзя было потому, что мать теперь держалась за сына, как за последнюю приманку жизни; и потому, несмотря на нежелание оставаться в Москве в кругу людей, знавших его прежде, несмотря на свое отвращение к статской службе, он взял в Москве место по статской части и, сняв любимый им мундир, поселился с матерью и Соней на маленькой квартире, на Сивцевом Вражке.