ПоследовательностьL - SequenceL

ПоследовательностьL
Парадигмы Параллельные вычисления , Функциональное , Чисто функциональное , Декларативное программирование
Разработано Д-р Дэниел Кук,
д-р Нельсон Раштон,
д-р Брэд Неманич
Разработчики Техасский технический университет,
Texas Multicore Technologies
Впервые появился 1989 ; 32 года назад  ( 1989 )
Печатная дисциплина Статический , вывод типа
Платформа x86 , ПИТАНИЕ , ARM
Операционные системы Windows , macOS , Linux
Лицензия Проприетарный
Веб-сайт texasmulticore .com

SequenceL - это функциональный язык программирования общего назначения, компилятор и набор инструментов с автоматическим распараллеливанием ( параллельные вычисления ), основными задачами проектирования которого являются производительность на многоядерном процессоре , простота программирования, переносимость / оптимизация платформы, а также ясность и читаемость кода. Его главное преимущество заключается в том, что его можно использовать для написания простого кода, который автоматически полностью использует всю доступную вычислительную мощность, без необходимости заботиться программистами об определении параллелизма , указании векторизации , избежании состояний гонки и других проблемах, связанных с ручным управлением на основе директив. подходы к программированию, такие как OpenMP .

Программы, написанные на SequenceL, могут быть скомпилированы в многопоточный код, который выполняется параллельно, без явных указаний программиста о том, как и что распараллеливать. По состоянию на 2015 год версии компилятора SequenceL генерируют параллельный код на C ++ и OpenCL , что позволяет ему работать с большинством популярных языков программирования, включая C , C ++, C # , Fortran , Java и Python . Среда выполнения, зависящая от платформы, безопасно управляет потоками, автоматически обеспечивая параллельную производительность в соответствии с количеством доступных ядер, в настоящее время поддерживая платформы x86 , POWER8 и ARM .

История

SequenceL изначально разрабатывался в течение 20 лет, начиная с 1989 года, в основном в Техасском техническом университете . Основное финансирование было от НАСА , которое изначально стремилось разработать язык спецификаций, который был бы «самопроверяющимся»; то есть после написания требования могут быть выполнены , а результаты проверены на соответствие желаемому результату.

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

По мере развития языка исследователи разрабатывали новые вычислительные подходы, в том числе потребляли-упрощали-производили (CSP). В 1998 году начались исследования по применению SequenceL для параллельных вычислений . Это достигло кульминации в 2004 году, когда оно приняло более полную форму с добавлением семантики нормализации-транспонирования (NT), что совпало с тем, что основные поставщики центральных процессоров (ЦП) сделали большой переход на многоядерные процессоры вместо того, чтобы продолжать увеличить тактовую частоту. NT - это семантическая рабочая лошадка, используемая для упрощения и декомпозиции структур на основе стратегии выполнения, подобной потоку данных , аналогичной GAMMA и NESL. Семантика NT достигает цели, аналогичной цели исключения шаблонов Леммеля и Пейтон-Джонса. Все остальные особенности языка определяются этими двумя законами, включая рекурсию , структуры нижних индексов, ссылки на функции и вычисление тел функций.

Хотя это не было первоначальной целью, эти новые подходы позволили языку распараллелить большую часть выполняемых им операций, прозрачно для программиста. В 2006 году в Техасском техническом университете был разработан прототип компилятора с автоматическим распараллеливанием. В 2009 году Texas Tech передала лицензию на интеллектуальную собственность Texas Multicore Technologies (TMT) для последующей коммерческой разработки. В январе 2017 года TMT выпустила версию 3, которая включает бесплатную версию Community Edition для загрузки в дополнение к коммерческой версии Professional Edition.

Дизайн

SequenceL спроектирован так, чтобы быть максимально простым в изучении и использовании, с упором на алгоритмический код, который добавляет ценность, например, изобретатели решили не изобретать ввод-вывод заново, поскольку C хорошо справился с этим. В результате полный справочник по языку SequenceL занимает всего 40 страниц с многочисленными примерами, а его формальная грамматика содержит около 15 производственных правил.

SequenceL строго оценивается (как Lisp ), статически типизируется с выводом типа (как Haskell ) и использует комбинацию инфиксных и префиксных операторов, которые напоминают стандартные неформальные математические обозначения (например, C , Pascal , Python и т. Д.). Это чисто декларативный язык, означающий, что программист определяет функции в математическом смысле, не давая инструкций по их реализации. Например, математическое определение умножения матриц выглядит следующим образом:

Продукт м × р матрицы А с р х п матрицы B является т × п матрица, ( я , J ) -й запись

Определение SequenceL более или менее точно отражает это определение: 

   matmul(A(2), B(2)) [i,j] := 
       let k := 1...size(B); 
       in  sum( A[i,k] * B[k,j] );

Нижние индексы, следующие за каждым параметром A и B в левой части определения, указывают, что A и B являются структурами глубины 2 (т. Е. Списками списков скаляров), которые здесь рассматриваются как матрицы. Из этого формального определения SequenceL выводит размеры определенного продукта по формуле для его ( i , j ) -й записи (как набора пар ( i , j ), для которых определена правая часть) и вычисляет каждую запись по той же формуле, что и в неформальном определении выше. Обратите внимание, что в этом определении нет явных инструкций для итерации или порядка, в котором должны выполняться операции. Из-за этого компилятор SequenceL может выполнять операции в любом порядке (включая параллельный), который удовлетворяет определяющему уравнению. В этом примере вычисление координат в продукте будет распараллелено таким образом, что для больших матриц масштабируется линейно с количеством процессоров.

Как отмечалось выше, SequenceL не имеет встроенных конструкций для ввода / вывода (I / O), поскольку он был разработан для аддитивной работы с другими языками программирования. Решение о компиляции в многопоточный C ++ и поддержке 20+ языков Simplified Wrapper и Interface Generator ( SWIG ) (C, C ++, C #, Java, Python и т. Д.) Означает, что он легко вписывается в существующие потоки проектирования, обучение и инструменты. Его можно использовать для улучшения существующих приложений, создания многоядерных библиотек и даже для создания автономных приложений путем связывания полученного кода с другим кодом, который выполняет задачи ввода-вывода. Функции SequenceL также можно запрашивать из интерпретатора с заданными входными данными, например Python и других интерпретируемых языков.

Нормализовать – транспонировать

Основная нескалярная конструкция SequenceL - это последовательность, которая по сути является списком. Последовательности могут быть вложенными на любой уровень. Чтобы избежать рутинного использования рекурсии, распространенной во многих чисто функциональных языках, SequenceL использует технику, называемую нормализацией-транспонированием (NT), в которой скалярные операции автоматически распределяются по элементам последовательности. Например, в SequenceL у нас есть

Это происходит не из-за перегрузки оператора '+', а из-за эффекта NT, который распространяется на все операции, как встроенные, так и определяемые пользователем. В качестве другого примера, если f () - это функция с 3 аргументами, аргументы которой являются скалярами, то для любых подходящих x и z мы будем иметь

Конструкция NT может использоваться для нескольких аргументов одновременно, как, например, в

Это также работает, когда ожидаемый аргумент не является скаляром любого типа T, а фактический аргумент - это список объектов типа T (или, в более общем смысле, любая структура данных, координаты которой имеют тип T). Например, если A - это матрица, а X s - это список матриц [X 1 , ..., X n ], и, учитывая приведенное выше определение умножения матриц, в SequenceL мы будем иметь 

   matmul(A,Xs) = [matmul(A,X1),...,matmul(A,Xn)]

Как правило, NT устраняют необходимость в итерациях, рекурсиях или функциональных операторах высокого уровня для

  1. делать то же самое с каждым членом структуры данных или с
  2. обрабатывать вместе соответствующие части конструкций одинаковой формы.

Это, как правило, объясняет большинство случаев использования итерации и рекурсии.

Пример: простые числа

Хороший пример, демонстрирующий вышеупомянутые концепции, - это поиск простых чисел. Простое число определено как

Целое число больше 1 без положительных делителей, кроме него самого и 1.

Таким образом, положительное целое число z является простым, если никакие числа от 2 до z -1 включительно не делятся поровну. SequenceL позволяет запрограммировать эту проблему, буквально транскрибируя приведенное выше определение на язык.

В SequenceL последовательность чисел от 2 до z -1 включительно равна (2 ... ( z -1)), поэтому программу для поиска всех простых чисел от 100 до 200 можно записать: 

   prime(z) := z when none(z mod (2...(z-1)) = 0);

Который на английском просто говорит:

... вернуть аргумент, если ни одно из чисел от 2 до 1 не меньше самого аргумента, делится на него поровну.

Если это условие не выполняется, функция ничего не возвращает. В результате запуск этой программы дает 

   cmd:>prime(17)
   17
   cmd:>prime(18)
   empty

Строка «от 100 до 200» в программе не появляется. Скорее, программист обычно передает эту часть в качестве аргумента. Поскольку программа ожидает скаляр в качестве аргумента, передача ей вместо этого последовательности чисел заставит SequenceL автоматически выполнить операцию над каждым членом последовательности. Поскольку функция возвращает пустое значение для ошибочных значений, результатом будет входная последовательность, но отфильтрованная для возврата только тех чисел, которые удовлетворяют критериям для простых чисел: 

   cmd:>prime(100...200)
   [101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199]

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

Составные части

Следующие программные компоненты доступны и поддерживаются TMT для использования при написании кода SequenceL. Все компоненты доступны на платформах x86 под управлением Windows , macOS и большинства разновидностей Linux (включая CentOS , RedHat , OpenSUSE и Ubuntu ), а также на платформах ARM и IBM POWER под управлением большинства разновидностей Linux .

Устный переводчик

Командной строки интерпретатор позволяет писать код непосредственно в командную оболочку или загрузки кода из заранее написанных текстовых файлов. Этот код может быть выполнен, а результаты оценены, чтобы помочь проверить правильность кода или найти быстрый ответ. Он также доступен через популярную интегрированную среду разработки Eclipse (IDE). Код, выполняемый в интерпретаторе, не выполняется параллельно; он выполняется в одном потоке.

Компилятор

Компилятор командной строки считывает код SequenceL и генерирует сильно распараллеленный, векторизованный , C ++ и, возможно, OpenCL, который для выполнения должен быть связан с библиотекой времени выполнения SequenceL.

Время выполнения

Среда выполнения - это предварительно скомпилированный набор библиотек, который работает со скомпилированным распараллеленным кодом C ++ для оптимального выполнения на целевой платформе. Он основан на Intel Threaded Building Blocks (TBB) и занимается такими вещами, как оптимизация кэша, управление памятью, кража рабочих очередей и мониторинг производительности.

Плагин Eclipse IDE с отладчиком

Eclipse , интегрированная среда разработки плагин предоставляет стандартные возможности редактирования (функции накопительного пакета, chromacoding и т.д.), а также SequenceL отладки среды. Этот плагин работает с интерпретатором SequenceL, поэтому его нельзя использовать для отладки многопоточного кода; однако, обеспечивая автоматическое распараллеливание, отладка параллельного кода SequenceL действительно проверяет правильность последовательного кода SequenceL. То есть, если он работает правильно последовательно, он должен работать правильно и параллельно - поэтому достаточно отладки в интерпретаторе.

Библиотеки

Различные математические и другие стандартные библиотеки функций включены в качестве исходного кода SequenceL для упрощения процесса программирования и служат в качестве примеров передовой практики. Их можно импортировать почти так же, как библиотеки C или C ++ #included.

Смотрите также

Рекомендации

Внешние ссылки