SequenceL - SequenceL

SequenceL
Парадигмы	Параллельные вычисления, Функциональный, Чисто функциональный, Декларативное программирование
Разработано	Доктор Дэниел Кук,; Доктор Нельсон Раштон,; Доктор Брэд Неманич
Разработчики	Техасский технический университет,; Техасские многоядерные технологии
Впервые появился	1989; 31 год назад
Печатная дисциплина	Статический, вывод типа
Платформа	x86, МОЩНОСТЬ, РУКА
Операционные системы	Windows, macOS, Linux
Лицензия	Проприетарный
Интернет сайт	Texasmulticore.com[мертвая ссылка ]

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

Программы, написанные на SequenceL, могут быть скомпилированы в многопоточный код, который выполняется параллельно, без явных указаний программиста, как и что распараллеливать. По состоянию на 2015 год^{[Обновить]}, версии SequenceL компилятор генерировать параллельный код в C ++ и OpenCL, что позволяет ему работать с большинством популярных языков программирования, включая C, C ++, C #, Фортран, Ява, и Python. Среда выполнения, зависящая от платформы, безопасно управляет потоками, автоматически обеспечивая параллельную производительность в соответствии с количеством доступных ядер, которые в настоящее время поддерживают x86, МОЩНОСТЬ8, и РУКА платформы.

История

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

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

По мере развития языка исследователи разработали новые вычислительные подходы, в том числе потреблять-упрощать-производить (CSP).^[3] В 1998 году начались исследования по применению SequenceL для параллельные вычисления. Кульминацией этого стал 2004 год, когда он принял более полную форму с добавлением нормализовать-транспонировать (NT) семантический,^[4]^[5] что совпало с основными поставщиками центральные процессоры (Процессоры) переходят на многоядерные процессоры вместо того, чтобы продолжать увеличивать тактовые частоты. NT - семантическая рабочая лошадка, используемая для упрощения и декомпозиции структур на основе поток данных -подобная стратегия исполнения, аналогичная ГАММА^[6] и NESL.^[7] Семантика NT достигает цели, аналогичной цели устранения шаблонного кода Лэммеля и Пейтон-Джонса.^[8]^[9] Все остальные особенности языка определяются этими двумя законами, включая рекурсия, индексирование структур, ссылки на функции и оценка тел функций.^[10]^[11]

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

Дизайн

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

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

Продукт м×п матрица А с п×п матрица B это м×п матрица, чья (я,j) ая запись

{ Displaystyle сумма _ {к = 1} ^ {р} А (я, к) В (к, j)}

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

   matmul (A (2), B (2)) [i, j]: = let k: = 1 ... size (B); в сумме (A [i, k] * B [k, j]);

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

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

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

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

{ displaystyle [1,2,3] +10 == [11,12,13]}

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

{ Displaystyle f (x, [1,2,3], z) == [f (x, 1, z), f (x, 2, z), f (x, 3, z)]}

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

{ Displaystyle [1,2,3] + [10,20,30] == [11,22,33]}

Он также работает, когда ожидаемый аргумент не является скаляром любого типа T, а фактический аргумент представляет собой список объектов типа T (или, в более общем смысле, любую структуру данных, координаты которой имеют тип T). Например, если А матрица и Икс_s список матриц [X₁, ..., ИКС_п], и учитывая приведенное выше определение умножения матриц, в SequenceL мы имели бы

   матмул (A, X_s) = [matmul (A, X₁), ..., matmul (A, X_п)]

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

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

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

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

Хорошим примером, демонстрирующим вышеуказанные концепции, может быть поиск простых чисел. А простое число определяется как

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

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

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

   prime (z): = z, когда нет (z mod (2 ... (z-1)) = 0);

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

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

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

   cmd:> prime (17) 17 cmd:> prime (18) пусто

Строка «от 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, Красная шляпа, OpenSUSE, и Ubuntu ) и на РУКА и IBM POWER платформы с большинством разновидностей Linux.

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

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

Компилятор

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

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

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

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

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

Библиотеки

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

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

внешняя ссылка

[Licensing-1] «Лицензирование SequenceL». Архивировано из оригинал на 2017-02-02. Получено 2017-01-26.

[2] "Доктор Дэниел Кук из Texas Multicore Technologies". Архивировано из оригинал на 2016-03-04. Получено 2016-02-24.

[3] «Потребляйте-упрощайте-производите (CSP)» (PDF). Архивировано из оригинал (PDF) на 2017-02-02. Получено 2017-01-26.

[4] Неманич, Брэд; Кук, Дэниел; Раштон, Нельсон (2010), SequenceL: прозрачность и многоядерный параллелизм (PDF), DAMP '10 Труды 5-го семинара ACM SIGPLAN по декларативным аспектам многоядерного программирования, Нью-Йорк, Нью-Йорк, США: ACM, стр. 45–52, заархивировано оригинал (PDF) на 2017-02-02, получено 2017-01-26

[5] Кук, Дэниел; Раштон, Нельсон; Неманич, Брэд; Уотсон, Роберт Дж .; Андерсен, Пер (март 2008 г.), «Нормализация, транспонирование и распределение: автоматический подход для обработки нескаляров», Транзакции ACM по языкам и системам программирования, 30 (2): 1–49, Дои:10.1145/1330017.1330020

[6] Banater, JP; Ле Метайер, Д. (январь 1993 г.), «Программирование с помощью преобразования мультимножества» (PDF), Коммуникации ACM, 36 (1): 98–111, Дои:10.1145/151233.151242

[7] Блеллох, Гай (март 1996 г.), "Программирование параллельных алгоритмов", Коммуникации ACM, 39 (3): 85–97, CiteSeerX 10.1.1.141.5884, Дои:10.1145/227234.227246

[8] Лэммель, Ральф; Пейтон-Джонс, Саймон (2003), «Избавьтесь от своего шаблона: практический шаблон проектирования для общего программирования», Протоколы TLDI 2003

[9] Лэммель, Ральф; Пейтон-Джонс, Саймон (2004), «Избавьтесь от шаблонов: отражение, застежки-молнии и обобщенные преобразования», Материалы ICFP 2004

[10] Кук, Дэниел; Раштон, Нельсон (январь 1993 г.), «Итеративное и параллельное проектирование алгоритмов на основе языковых следов высокого уровня» (PDF), ICCS'05 Труды 5-й Международной конференции по вычислительной науке, Часть III: 891–894, Дои:10.1007/11428862_132, ISBN 978-3-540-26044-8, заархивировано из оригинал (PDF) на 2017-02-02, получено 2017-01-26

[11] Кук, Дэниел; Раштон, Нельсон (27–30 июня 2005 г.), «SequenceL - Обзор простого языка», Труды Международной конференции по языкам программирования и компиляторам 2005 г., PLC 2005

[12] Texas Multicore Technologies, Inc.

[13] Неманич, Брэд; Кук, Дэниел; Раштон, Нельсон (2010), SequenceL: прозрачность и многоядерный параллелизм (PDF), DAMP '10 Труды 5-го семинара ACM SIGPLAN по декларативным аспектам многоядерного программирования, Нью-Йорк, Нью-Йорк, США: ACM, стр. 45–52, заархивировано оригинал (PDF) на 2017-02-02, получено 2017-01-26

[14] Кук, Дэниел; Раштон, Нельсон (27–30 июня 2005 г.), «SequenceL - Обзор простого языка», Труды Международной конференции по языкам программирования и компиляторам 2005 г., PLC 2005

[15] Блоки Intel Threaded Building Blocks (TBB)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]