Марк Фрили, университет Монреаля
В данной статье описывается техника реализации для конструкции Multilisp future, рассчитанную на большие мультипроцессорные системы с разделяемой памятью. Данная техника является одной из разновидностей ленивых вычислений. Оригинальная реализация ленивых вычислений описана в [Mohr, 1991], основывается на эффективно разделяемой памяти для распределения задач между процессорами. Нами же предлагается метод распределения , основанный на парадигме передачи сообщений. Основными преимуществами являются простота реализации, меньшая стоимость запуска локальных задач, возможность полного кеширования стека на некогерентных машинах. Тестирование проводилось на 32 процессорном BBN TC2000 и показало, что наш метод более эффективен чем оригинальная реализация в 2 раза.
Multilisp
[Halstead, 1985]
расширяет
язык
программирования
Scheme [IEEE
Std
1178-1990,1991] простой
и элегантной
парадигмой
программирования.
Параллелизм
непосредственно
указывается
в программе
благодаря
использованию
специальной
формы future.
Выражение
(future
expr)
называется future и expr его тело. Параллелизм следует из модели задач. Когда задача выполняет future, она порождает подзадачу (задачу потомка) для вычисления тела future. Основная же задача начинает выполнять продолжение future. Таким образом, параллелизм существует между вычислением тела и продолжением основной задачи.
Концептуально, значение, возвращаемое в продолжение, есть вычисляемое (не обязательно вычисленное) значение тела. Парадокс избегается используя специальный замещающий объект – placeholder, чтобы представить значение тела. Замещающий объект изначально пуст и получает определенное значение только тогда, когда подзадача его вернет. Когда замещающий объект передается строгой функции, например car или if в качестве условия, он должен быть определен (тронут), чтобы получить значение. Если же он не определен, то задача откладывается до определения его подзадачей.
В дополнение Multilisp использует модель общей памяти. Это означает, что задача может обращаться к любым данным, вне зависимости от того, где они были созданы.
Eager task creation (ETC - Создание нетерпеливой задачи) – прямая реализация future, используемая в некоторых параллельных Лисп системах [Halstead, 1984,Steinberg et al.,1986 Goldman and Gabriel, 1988, Miller, 1988, Zorn et al.,1988, Swanson et al.,1988, Kranz et al.,1989]. Вычисление future немедленно создает в куче объект задачу для представления порожденной задачи и делает ее доступной всем процессорам, добавляя ее в глобальную очередь задач: рабочую очередь. Объект задача состоит из продолжения выполнения, показывающего состояние задачи. Это продолжение установлено на вычисление тела future и затем на определение замещающего объекта для результата. Когда процессор освобождается, он удаляет задачу из рабочей очереди и продолжает ее выполнение продолжения. Для уменьшения загрузки, рабочая очередь распределена между машинами, и каждый процессор порождает и выполняет задачи со своей рабочей очереди. Когда процессор свободен и его рабочая очередь пуста, он должен получит задачу из рабочей очереди другого процессора. Передача задачи от жертвы(victim) к вору(thief) называется кражей(steal).
Рисунок
1- ETC в действии
Основной недостаток ETC – высокая загрузка управления задачами. Считая что каждая задача случайным образом выполняется и завершается, для каждой задачи необходимо выполнение следующих операций.
При порождении задачи:
1 Создать объект задачу и объект заместитель
2 Создать среду для запуска тела future
3 Добавить задачу в рабочую очередь (требует блокировать очередь, потом разблокировать)
При продолжении задачи:
4 Забрать задачу из очереди (требует блокировки/разблокировки очереди)
5 Начать продолжение выполнения задачи
При завершении задачи
6 Определить объект заместитель (также должен блокироваться, затем разблокироваться чтобы избежать гонок за него)
7 Передача отложенных задач в рабочую очередь
Общая стоимость этих операций может легко превзойти сотни машинных инструкций. Производительность существующих реализаций ETC подтверждают это. Система Mul-T была аккуратно разработана чтобы минимизировать стоимость ETC [Kranz et. Al.,1989] и у нее это занимает около 130 машинных инструкций на задачу на Encore Multimax. На других системах стоимость еще выше, например в Qlisp на Alliant FX/8 около 1400 инструкций.
Из за высокой стоимости распараллеливания, результат сильно зависит от размера задач, так как для маленьких задач большая часть времени будет потрачена на бесполезное порождение задачи.
Lazy Task Creation (LTC – Создание ленивой задачи) есть альтернатива реализации future, предложенная [Kranz et.al., 1989], реализованная и изученная Eric Mohr на Encore Multimax [Mohr 1991]. Реализация LTC, описанная в этом разделе именно та, которую использовал Mohr и будет называться протоколом общей памяти (shared memory SM) , так как считается для общей памяти. LTC уменьшает стоимость вычисления future благодаря отложению вычислений, а во многих случаях и вообще без порождения новой задачи. В сущности, новая задача порождается только в случае, если процессор простаивает. LTC достигает этого адаптируя стековое расписание задач, которое в отсутствии свободных процессоров производит такой же порядок действий, что и последовательная программа (т.е. без future). Вычисление тела future немедленно начинается, а продолжение выполнения программы откладывается. Каждый процессор содержит свою структуру данных отложенных вычислений, подобную стеку, называемую очередью ленивых задач (LTQ – lazy task queue). Когда вычисление тела завершается, последняя отложенная задача удаляется из очереди и начинает выполняться. Это обязательно продолжение выполнения после future. Отметим что нет необходимости создавать объект заместитель, так как продолжение может непосредственно получить значение, возвращенное телом.
В LTC, кража задачи происходит, убирая самое старое продолжение из LTQ жертвы, затем созданием соответствующего объекта заместителя и новой задачи, передачи задачи вору. Для связи между украденной задачи с ее потомком, вор должен вычислить продолжение задачи с созданным заместителем. Заместитель также должен храниться в порожденной задаче, чтобы правильно определить место для результата.
Рисунок 2 - LTC в действии
Кража самой старой задачи по сравнению с самой новой имеет следующие преимущества:
1 Оно может сократить количество краж, потому что старые задачи обычно содержат в себе больше работы (вор будет дольше занят обработкой задач до следующей кражи). Это верно для программ, написанных с использованием «разделяй и властвуй» параллельных алгоритмов. Если алгоритм хорошо сбалансирован, объем работ украденной задачи будет соизмерим с суммой оставшихся в LTQ работ.
2 Доступ к LTQ более эффективный, так как два конца LTQ могут работать независимо. Жертва может добавлять продолжение в LTQ в то время когда вор совершает кражу с другого конца.
Стековое представление расписания LTC задач позволяет эффективную реализацию помещения задачи в стек и извлечения из него. Основная идея заключается в том, что задачи не обязаны копироваться или перемещаться со стека. На самом деле LTQ это очередь с двумя концами с указателями на стек продолжений. На рисунке 3 показано состояние стека и LTQ для Р4 до и после кражи (заметьте, что связь на рисунке условная). Изначально указатели на голову и хвост LTQ равны и указатель на дно стека непосредственно следует за головой. Полезный инвариант - то, что указатель на дно стека всегда под вершиной стека, причем на дне самая старая задача. Механизм связи задач вставляет и удаляет тела задач, как и должно быть. Каждое тело задачи содержит адрес возврата, когда тело будет удалено со стека. Когда вычисляется future, продолжение попадает в стек как указатель на текущее тело. Удаление продолжения после выполнения тела должно быть выполнено осторожно, так как другой процессор в это же время может красть эту задачу. Если LTQ не пуста, т.е. голова и хвост не равны, хвост уменьшается и результаты вычисления тела записываются. Если LTQ пуста, то это означает, что продолжение уже украдено вместе с местом для результата и процессору нечего делать.
Рисунок 3 - Механизм кражи