УВЕЛИЧЕНИЕ ПРОИЗВОДИТЕЛЬНОСТИ ТРАНСЛЯТОРА ЯЗЫКА ЛИСП БЛАГОДАРЯ ИСПОЛЬЗОВАНИЮ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

Савков К

Донецкий национальний технический университет

Уже сегодня рынок персональных компьютеров практически перешел на многоядерные и мультипроцессорные системы, в связи с этим от современного программного обеспечения требуется полное использование современных возможностей аппаратуры. При этом последовательные программы необходимо переделывать в их параллельный эквивалент благодаря рефакторингу. Сам рефакторинг программного обеспечения требует экономических затрат и многих человеко/часов работы. На сегодняшний день решение данной проблемы частично автоматизировано, в основном благодаря глубокому анализу на этапе компиляции программы. Проще дела обстоят с программами для виртуальных машин, где в основном доработке подвергается только виртуальная машина, а не сами программы. При этом новые виртуальные машины достигают увеличения производительности за счет распараллеливания внутренних задач, таких как сборка мусора, поиск в таблице символов и.т.д. Такие виртуальные машины фактически не распараллеливают программу, а увеличивают скорость ее выполнения за счет снижения внутренних задержек. Основным преимуществом данного подхода является то, что прирост производительности происходит сразу во время выполнения, не требуя при этом предварительной обработки текста программы. Данная работа призвана объединить в себе эти два подхода в рамках транслятора языка Лисп. 

Сама идея использования параллельных вычислений в языке Lisp не нова, множество реализаций трансляторов языка Лисп позволяют порождать новые процессы для выполнения подзадач. Первыми решениями для параллельного выполнения Lisp программ были дополнительно введенные функции операционной системы по работе с процессами и другими системными объектами. Стандарт Common Lisp определил механизм вызова системных функций, однако в разных операционных системах эти функции были разными. Другим решением для распараллеливания программ на Лиспе было введение дополнительных языковых конструкций для определения параллельного выполнения. Данные расширения языка назывались условно прозрачными, так как без них результаты  последовательного выполнения программы должны были совпадать с результатами параллельного выполнения программы. Одна из таких конструкций – “future” была занесена в стандарт языка для порождения отложенных вычислений. Она определяла место для будущего результата параллельного вызова функции и продолжала дальнейшее выполнение основной программы. Если к моменту обращения к результату отложенного вызова результата еще не было, то программа ждала его вычисления.

Устоявшиеся реализации параллельного Лиспа:

Kyoto Common Lisp (университет Киото) – 1985,AOS/VS для ECLIPSE MV, Unix 4.2 bsd для Sun Workstation (на базе Motorola 6800), для распараллеливания используются функции ОС.

MultiLisp 1985 – Использование конструкций “future”  в 1991 году стало стандартом Лиспа.

BandaLisp (университет Сингапура) – 1994,SunOS 5.3 SunSparc Server 1000 (мультипроцессорная система с разделяемой памятью) для распараллеливания используются специально введенные конструкции для перевода списка в массивы и компиляция  программы.

Qlisp (Lucid Inc) – 1989 (мультипроцессорная система с разделяемой памятью), для распараллеливания введены специальные конструкции языка, при этом виртуальная машина динамически подстраивается под число занятых процессоров и представляет языковые средства синхронизации.

TS/SCHEME (NEC) - 1994,STING, Silicon Graphics MIPS R4000 (распределенная система для объектно-ориентированного Лиспа), используются  специальные конструкции языка.

MultiLisp (университет Монреаля) – 1993, реализация “future” через MPI.

Начиная с 1995 года интерес к Лиспу упал, этим объясняется отсутствие литературы за данный период. В период с 2000 по 2007 год новых подходов к распараллеливанию Лиспа не формировалось, появилось несколько реализаций Лиспа с открытым кодом на различные платформы, при этом используемые методы остались те же.  Большинство данных реализаций рассчитано на специальные мультипроцессорные системы. Все реализации требуют использования дополнительных конструкций языка, непосредственно указываемых при написании программы. Данная особенность делает реализации неспособными к распараллеливанию уже имеющихся последовательных программ без дополнительной переработки исходных текстов.

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

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

Таким образом, создаваемый транслятор будет служить средством распараллеливания динамически формируемых программ, обеспечивая при этом увеличение производительности за счет распараллеливания их выполнения. Может использоваться как средство анализа последовательных программ. 

Литература

1.      Moreau Luc. An operational semantics far a parallel functional language with   continuations, University of Liege - Belgium,1991. - 32 p.

2.      Freely Marc, Miller James S. A parallel virtual machine for efficient scheme compilation, Brandeis University - Waltham,1994. - 36 p.

3.      Tanaka Tomoyuki, Uzuhara Shigeru. Futures and multiple values in parallel Lisp, Lisp Conference,1992. – 16 p.

4.      Feng M.D., Wong W.F., Yuen C.K. Compiling parallel Lisp for a shared memory multiprocessor, National University of Singapore, 1994. – 27p.

5.      Goldman Ron, Gabriel Richard P. Qlisp: Parallel processing in Lisp, Lucid Inc.,1993. – 24 p.

6.      Freely Marc. A message passing implementation of lazy task creation Montreal University,1993. -16 p.