Материалы по теме выпускной работы: Реферат | Библиотека | Ссылки | Отчет о поиске | Индивидуальное задание

Уже сегодня рынок персональных компьютеров практически перешел на многоядерные и мультипроцессорные системы, в связи с этим от современного программного обеспечения требуется полное использование современных возможностей аппаратуры. При этом последовательные программы необходимо переделывать в их параллельный эквивалент  для увеличения быстродействия- рефакторинг. Сам рефакторинг программного обеспечения требует экономических затрат и многих человеко/часов работы. При этом фактически ничего нового не создается, т.е. переделанная программа не будет обладать новыми функциональными возможностями. Кроме того, программное обеспечение при сегодняшних темпах развития создается намного быстрее, чем успешно проходит тестирование, а даже после успешного  тестирования никто не застрахован от ошибок. Компании, производящие программное обеспечение терпят колоссальные убытки и теряют своих покупателей в случае, если критическая ошибка не была устранена вовремя. Наиболее остро данная проблема стоит в игровой индустрии. Из-за огромной конкуренции игры в большинстве своем делаются ускоренно и не редки случаи, когда уже поступившая в продажу компьютерная игра не рабочая. При таком положении дел опытные разработчики пользуются проверенными временем решениями, а не пишут свои собственные реализации. Таким образом, люди склонны пользоваться стабильным и надежным программным обеспечением, которое, в свою очередь тоже прошло тернистый путь доработок и исправления ошибок. Недостатки рефакторинга на данный момент перевешивают его преимущества, поэтому рефакторингом старого программного обеспечения практически не занимаются. В целом данный подход целиком логичен, ведь зачем переделывать программу, которая и так отлично работает? Стоит отметить, что многие старые программы, несмотря на старые подходы к построению, являются отличными образцами, причем часто выполнены лучше, чем современные аналоги. Естественно предположить, что при рефакторинге таких программ  их очень сложно улучшить, не сделав ошибок. Человек склонен делать ошибки, это естественный ход вещей, так как человек учится на своем опыте и извлекает даже из ошибок какую-то пользу. Традиционно считается, что машина не делает ошибок, или делает их намного реже, хотя машины и делают люди. В этом плане рефакторинг относится к тем вещам, которые лучше делать без ошибок. Тем не менее, на данном этапе развития, мы еще не обладаем должными машинами, способными на качественное воспроизводство человеческой умственной деятельности. Рефакторинг программного обеспечения в общем случае требует от человека интеллектуального подхода, хотя часто он заключается лишь в замене некоторых операций на более быстродействующие. Ярким примером такого рефакторинга является переделка суммирования массивов с использованием MMX или SSE. Получаемые в результате данных переделок программы являют собой эквивалент оригинальной программы, за исключением того, что выполняются в несколько раз быстрее.

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

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

Одной из подобных систем является Лисп системы. Лисп является функциональным языком, в котором текст и данные программы представлены одинаково. Кроме этого сам механизм виртуальной машины довольно прост в реализации. Язык Лисп является вторым по счету языком высокого уровня и изначально был придуман для работы со списками (List Processing). Данная его особенность ориентировала его на подмножества натурального языка, делая его удобным для решения задач искусственного интеллекта. Рекурсия и лямбда-выражения сделали язык удобным для математических исследований, а также для создания баз данных. Язык логического программирования – Prolog, как ни странно очень просто реализуется на языке Лисп. Идея рекурсивного параллелизма в данном языке так же стара, как и он сам. Дело в том, что все выполнение Лисп программы основано на рекурсии. 

Предметом исследования является модель транслятора языка Лисп, обладающего возможностью параллельного выполнения программ, а также увеличивающего их производительность.

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

Kyoto Common Lisp (университет Киото) – 1985,AOS/VS для ECLIPSE MV, Unix 4.2 bsd для Sun Workstation (на базе Motorola 6800), для распараллеливания используются функции ОС. Данная реализация Лисп является наиболее полной и мощной. Все последующие реализации Common Lisp основывались на частях этой, часть функций перешла в стандарт Common Lisp. Данная реализация имела свой дополнительный интерфейс, написанный на Си. Кроме того, основные функции работы с ОС были перенесены из Си в Лисп, сохранив при этом даже назначение и порядок аргументов.

MultiLisp 1985 – Использование конструкций “future”. Данная дополнительная конструкция добавляла простой, эффективный и элегантный способ распараллеливания программ. Этот способ заключался в том, что тело данной конструкции вычислялось параллельно, а на место результата выполнения ставился заместитель. Когда основная программа доходила до места, где требовался результат, программа ожидала результат, в случае если он еще не вычислен параллельной задачей. Преимуществами данного подхода было то, что кроме этого он не вводил никаких других конструкций, связанных с синхронизацией, кроме того с заместителем можно было делать операции, не требующие знания результата, например конструировать список или брать следующий после него элемент.  Конструкция “future” в 1991 году стало стандартом Лиспа.

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

MultiLisp (университет Монреаля) – 1993, реализация “future” через MPI. В данной работе рассматриваются два основных метода управления задачами, называемые «Нетерпеливой задачей» и «Ленивой задачей». Благодаря их реализации подхода «Ленивой задачи» стало возможным существенное увеличение производительности на MPI, по сравнению с мультипроцессорами с разделяемой памятью. Основным недостатком MPI до их подхода являлась проблема синхронизации и передачи задач другим процессорам, так как были велики расходы процессорного времени на синхронизацию. Этим и объясняется обилие реализаций параллельного Лиспа для мультипроцессорных систем с общей памятью.

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

BandaLisp (университет Сингапура) – 1994,SunOS 5.3 SunSparc Server 1000 (мультипроцессорная система с разделяемой памятью) для распараллеливания используются специально введенные конструкции для перевода списка в массивы и компиляция  программы. Несмотря на то, что данная система рассчитана на последовательный диалект Лиспа Scheme, в ней применяется оптимизирующая компиляция частей программы в машинный код. Результатами данных преобразований стали очень высокие показатели быстродействия программы, часто достигающие результатов при решении данной задачи на параллельном Си. Целью данного проекта было опровержение того, что Лисп программы значительно проигрывают их эквивалентам, написанным на Си. Несмотря на успешный результат, данное негативное мнение о Лиспе все еще распространено.

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

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

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

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

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

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