2006 Ответы на экзаменационные вопросы по ПОД (Lilalbrother), страница 10

КомандаVLIW-процессора состоит из набора полей, каждое из которых отвечает за своюоперацию, например, за активизацию функциональных устройств, работу с памятью,операции с регистрами и т. п. Если какая-то часть процессора на данном этапевыполнения программы не востребована, то соответствующее поле команды незадействуется.Примером компьютера с подобной архитектурой может служить компьютер АР120В фирмы Floating Point Systems. Его первые поставки начались в 1976 году, а к 1980году по всему миру было установлено более 1600 экземпляров.

Команда компьютера АР-120В состоит из 64 разрядов и управляет работой всех устройств машины. Каждый такт(167 не) выдается одна команда, что эквивалентно выполнению 6 миллионов команд всекунду. Поскольку каждая команда одновременно управляет многими операциями, тореальная производительность может быть выше. Все 64 разряда команды АР-120В делятсяна шесть групп, отвечающих за свой набор операций: операции над 16-разряднымицелочисленными данными и регистрами, сложение вещественных чисел, управлениевводом/выводом, команды перехода, умножение вещественных чисел и команды работы сосновной памятью.Программа для VLIW-процессора всегда содержит точную информацию опараллелизме. Здесь компилятор всегда сам выявляет параллелизм в программе и явносообщает аппаратуре, какие операции не зависят друг от друга.

Код для VLIWпроцессоров содержит точный план того, как процессор будет выполнять программу:когда будет выполнена каждая операция, какие функциональные устройства будутработать, какие регистры какие операнды будут содержать и т. п. Компилятор VLIWсоздает такой план имея полное представление о целевом VLIW-процессоре, чего, вообщеговоря, нельзя сказать о компиляторах для суперскалярных машин.Оба подхода имеют свои достоинства и недостатки, и не стоит противопоставлятьпростоту и ограниченные возможности архитектуры VLIW сложности и динамическимвозможностям суперскалярных систем. Ясно, что создание плана выполнения операций вовремя компиляции важно для обеспечения высокой степени распараллеливания и вотношении суперскалярных систем.

Также ясно и то, что во время компиляциисуществует неоднозначность, которую можно разрешить только во время выполненияпрограммы с помощью динамических механизмов, свойственных суперскалярнойархитектуре.Большое влияние на развитие идей суперскалярной обработки еще в конце 50-хгодов прошлого столетия оказал проект STRETCH фирмы IBM, и сейчас архитектурамногих микропроцессоров построена по этому же принципу.

Яркими представителямиVLIW-компьютеров являются компьютеры семейств Multiflow и Cydra.29. Технологии параллельного программирования: способы и подходы30. Linda: общая концепция, пространство кортежей, примеры программ.Идея построения системы Linda исключительно проста, а потому красива и оченьпривлекательна. Параллельная программа есть множество параллельных процессов, икаждый процесс работает согласно обычной последовательной программе. Все процессыимеют доступ к общей памяти, единицей хранения в которой является кортеж. Отсюдапроисходит и специальное название для общей памяти - пространство кортежей. Каждыйкортеж это упорядоченная последовательность значений.

Например, ("Hello", 42, 3.14 ).Количество элементов в кортеже может быть любым.Все процессы работают с пространством кортежей по принципу: поместитькортеж, забрать, скопировать. В отличие от традиционной памяти, процесс может забратькортеж из пространства кортежей, после чего данный кортеж станет недоступнымостальным процессам. В отличие от традиционной памяти, если в пространство кортежейположить два кортежа с одним и тем же именем, то не произойдет привычного для нас"обновления" значения переменной - в пространстве кортежей окажется два кортежа содним и тем же именем. В отличие от традиционной памяти, изменить кортежнепосредственно в пространстве нельзя.

Для изменения значений элементов кортежа, егонужно сначала оттуда изъять, затем процесс, изъявший кортеж, может изменить значенияего элементов и вновь добавить измененный кортеж в память. В отличие от других системпрограммирования, процессы в системе Linda никогда не взаимодействуют друг с другомявно, и все общение всегда идет через пространство кортежей.Интересно, что с точки зрения системы Linda в любой последовательный языкдостаточно добавить лишь четыре новые функции, как он становится средствомпараллельного программирования! Эти функции и составляют систему Linda: три дляопераций над кортежами и пространством кортежей и одна функция для порожденияпараллельных процессов.Пример 1.По сути дела, описание системы закончено, и теперь можно привести нескольконебольших примеров.

Мы уже говорили о том, что параллельные процессы в системеLinda напрямую друг с другом не общаются, своего уникального номера-идентификаторане имеют и общего числа параллельно работающих процессов-соседей, вообще говоря, незнают. Однако если у пользователя есть в этом необходимость, то такую ситуацию оченьпросто смоделировать. Программа в самом начале вызывает функцию out:out( "Next", 1);Этот кортеж будет играть роль "эстафетной палочки", передаваемой от процессапроцессу: каждый порождаемый параллельный процесс первым делом выполнитследующую последовательность:in( "Next", formal My_Id);out( "Next", My_Id+1);Первый оператор изымает данный кортеж из пространства, на его основе процессполучает свой номер My_Id, и затем кортеж с номером для следующего процессапомещается в пространство.

Заметим, что использование функции in в данном случаепозволяет гарантировать монопольную работу с данным кортежем только одногопроцесса в каждый момент времени. После такой процедуры каждый процесс получитсвой уникальный номер, а число уже порожденных процессов всегда можно определить,например, с помощью такого оператора:read( "Next", formal Num_Processes);Пример 2.Теперь рассмотрим возможную схему организации программы для перемноженияС=A*B двух квадратных матриц размера N*N. Инициализирующий процесс используетфункцию out и помещает в пространство кортежей исходные строки матрицы A и столбцыматрицы B:out( "A",1, <1-я строка A>);out( "A",2, <2-я строка A>);...out( "B",1, <1-й столбец B>);out( "B",2, <2-й столбец B>);...Для порождения Nproc идентичных параллельных процессов можновоспользоваться следующим фрагментом:for( i = 0; i < Nproc; ++i )eval( "ParProc", get_elem_result() );Входные данные готовы, и нахождение всех N2 элементов Cij результирующейматрицы можно выполнять в любом порядке.

Главное - это распределить работу междупроцессами, для чего процесс, инициирующий вычисления, в пространство помещаетследующий кортеж:out( "NextElementCij", 1);Второй элемент данного кортежа всегда будет показывать, какой из N2 элементовCij предстоит вычислить следующим. Базовый вычислительный блок функцииget_elem_result() будет содержать следующий фрагмент:in( "NextElementCij", formal NextElement);if( NextElement < N*N )out("NextElementCij ", NextElement + 1);Nrow = (NextElement - 1) / N + 1;Ncol = (NextElement - 1) % N + 1;В результате выполнения данного фрагмента для элемента с номером NextElementпроцесс определит его местоположение в результирующей матрице: номер строки Nrow истолбца Ncol. Заметим, что если вычисляется последний элемент, то кортеж с именем"NextElementCij" в пространство не возвращается.

Когда в конце работы программыпроцессы обратятся к этому кортежу, они будут заблокированы, что не помешаетнормальному завершению программы. И, наконец, для вычисления элемента Cij каждыйпроцесс get_elem_result выполнит следующий фрагмент:read( "A", Nrow, formal row);read( "B", Ncol, formal col);out( "result", Nrow, Ncol, DotProduct(row,col) );где DotProduct это функция, реализующая скалярное произведение.

Таким образом,каждый элемент произведения окажется в отдельном кортеже в пространстве кортежей.Завершающий процесс соберет результат, поместив их в соответствующие элементыматрицы C:for ( irow = 0; irow < N; irow++)for ( icol = 0; icol < N; icol++)in( "result", irow + 1, icol + 1, formal C[irow][icol]);Пример 3.Не имея в системе Linda никаких явных средств для синхронизации процессов,совсем не сложно их смоделировать самому. Предположим, что в некоторой точке нужновыполнить барьерную синхронизацию N процессов. Какой-то один процесс, например,стартовый, заранее помещает в пространство кортеж ("ForBarrier", N).

Подходя к точкесинхронизации, каждый процесс выполняет следующий фрагмент, который и будетвыполнять функции барьера:in( "ForBarrier", formal Bar);Bar = Bar - 1;if( Bar != 0 ) {out( "ForBarrier", Bar);read( "Barrier" );} elseout( "Barrier" );Если кортеж с именем "ForBarrier" есть в пространстве, то процесс его изымает, впротивном случае блокируется до его появления.

Анализируя второй элемент данногокортежа, процесс выполняет одно из двух действий. Если есть процессы, которые еще недошли до данной точки, то он возвращает кортеж в пространство с уменьшенным наединицу вторым элементом и встает на ожидание кортежа "Barrier". В противном случаеон сам помещает кортеж "Barrier" в пространство, который для всех является сигналом кпродолжению работы.31. Linda: специальные функции для работы с пространством кортежей.Функция OUT помещает кортеж в пространство кортежей.

Например, out ("GoProcess", 5); помещает в пространство кортежей кортеж ("GoProcess", 5). Если такойкортеж уже есть в пространстве кортежей, то появится второй, что, в принципе, позволяетиметь сколь угодно много экземпляров одинаковых кортежей. По этой же причине спомощью функции out нельзя изменить кортеж, уже находящийся в пространстве.

Дляэтого кортеж должен быть сначала оттуда изъят, затем изменен и после этого помещенназад. Функция out никогда не блокирует выполнивший ее процесс.Функция IN ищет подходящий кортеж в пространстве кортежей, присваиваетзначения его элементов элементам своего параметра-кортежа и удаляет найденный кортежиз пространства кортежей.