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

ПоследовательностьL
Парадигмы	Параллельные вычисления , Функциональные , Чисто функциональные , Декларативное программирование
Разработано	Доктор Дэниел Кук, ; Доктор Нельсон Раштон, ; доктор Брэд Неманич
Разработчики	Техасский технологический университет, ; Техасские многоядерные технологии
Впервые появился	1989 год ; 35 лет назад
Дисциплина набора текста	Статический , вывод типа
Платформа	x86 , мощность , ARM
ТЫ	Windows , macOS , Linux
Лицензия	Собственный
Веб-сайт	техасский многоядерный .с [ мертвая ссылка ]

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

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

История [ править ]

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

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

По мере развития языка исследователи разработали новые вычислительные подходы, в том числе «потреби-упрости-производи » (CSP). ^[3] В 1998 году начались исследования по применению SequenceL для параллельных вычислений . Кульминацией этого стал 2004 год, когда он принял более полную форму с добавлением семантики нормализовать-транспонировать (NT), ^[4]^[5] это совпало с тем, что основные производители центральных процессоров (ЦП) перешли на многоядерные процессоры вместо того, чтобы продолжать увеличивать тактовую частоту. NT — это семантическая рабочая лошадка, используемая для упрощения и декомпозиции структур, основанная на стратегии выполнения, подобной потоку данных , аналогичной GAMMA. ^[6] и НЭСЛ. ^[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 строго оценивается (например, Lisp ), статически типизируется с выводом типа (например, Haskell ) и использует комбинацию инфиксных и префиксных операторов, которые напоминают стандартную, неформальную математическую нотацию (например, C , Pascal , Python и т. д.). Это чисто декларативный язык, то есть программист определяет функции в математическом смысле, не давая инструкций по их реализации. Например, математическое определение умножения матриц выглядит следующим образом:

Произведение размера m × p матрицы A на размера p × n матрицу B представляет собой матрицу размера m × n, ( i , j )-я запись которой равна

\sum _{k=1}^{p}A(i,k)B(k,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 and Interface Generator ( SIG ) (C, C++, C#, Java, Python и т. д.) означает, что оно легко вписывается в существующие процессы проектирования, обучение и инструменты. Его можно использовать для улучшения существующих приложений, создания многоядерных библиотек и даже создания автономных приложений путем связывания полученного кода с другим кодом, выполняющим задачи ввода-вывода. Функции SequenceL также можно запрашивать из интерпретатора с заданными входными данными, например Python и других интерпретируемых языков.

Нормализовать-транспонировать [ править ]

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

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

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

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

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

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

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

   matmul(A,X_s) = [matmul(A,X₁),...,matmul(A,X_n)]

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

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

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

Пример: простые числа [ править ]

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

Целое число, большее 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 (TBB). ^[15] и занимается такими вещами, как оптимизация кэша, управление памятью, кража рабочих очередей и мониторинг производительности.

Плагин Eclipse IDE с отладчиком [ править ]

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

Библиотеки [ править ]

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

См. также [ править ]

Ссылки [ править ]

^ «Лицензирование SequenceL» . Архивировано из оригинала 02 февраля 2017 г. Проверено 26 января 2017 г.
^ «Доктор Дэниел Кук из Texas Multicore Technologies» . Архивировано из оригинала 4 марта 2016 г. Проверено 24 февраля 2016 г.
^ «Потребляйте-упрощайте-производите (CSP)» (PDF) . Архивировано из оригинала (PDF) 02 февраля 2017 г. Проверено 26 января 2017 г.
^ Неманич, Брэд; Кук, Дэниел; Раштон, Нельсон (2010), SequenceL: Transparency And Multi-Core Parallelisms (PDF) , DAMP '10 Материалы 5-го семинара ACM SIGPLAN по декларативным аспектам многоядерного программирования, Нью-Йорк, Нью-Йорк, США: ACM, стр. 45–52. , заархивировано из оригинала (PDF) 2 февраля 2017 г. , получено 26 января 2017 г.
^ Кук, Дэниел; Раштон, Нельсон; Неманич, Брэд; Уотсон, Роберт Г.; Андерсен, Пер (март 2008 г.), «Нормализация, транспонирование и распределение: автоматический подход к обработке нескаляров», Транзакции ACM в языках и системах программирования , 30 (2): 1–49, doi : 10.1145/1330017.1330020 , S2CID 6833254
^ Банатер, JP; Ле Метайер, Д. (январь 1993 г.), «Программирование путем преобразования мультимножеств» (PDF) , Communications of the ACM , 36 (1): 98–111, doi : 10.1145/151233.151242 , S2CID 17076396
^ Блеллок, Гай (март 1996 г.), «Программирование параллельных алгоритмов», Communications of the ACM , 39 (3): 85–97, CiteSeerX 10.1.1.141.5884 , doi : 10.1145/227234.227246 , S2CID 12118850
^ Ламмель, Ральф; Пейтон-Джонс, Саймон (2003), «Откажитесь от шаблона: практический шаблон проектирования для универсального программирования», Proceedings of TLDI 2003.
^ Ламмель, Ральф; Пейтон-Джонс, Саймон (2004), «Откажитесь от шаблонов: отражение, молнии и обобщенные приведения», Труды ICFP 2004.
^ Кук, Дэниел; Раштон, Нельсон (январь 1993 г.), «Разработка итеративных и параллельных алгоритмов на основе языковых трассировок высокого уровня», ICCS'05 Proceedings of the 5th International Conference on Computational Science , vol. Часть III, стр. 891–894, doi : 10.1007/11428862_132 , ISBN. 978-3-540-26044-8
^ Кук, Дэниел; Раштон, Нельсон (27–30 июня 2005 г.), «SequenceL - обзор простого языка», Материалы Международной конференции 2005 г. по языкам программирования и компиляторам, PLC 2005 г.
^ Texas Multicore Technologies, Inc.
^ Неманич, Брэд; Кук, Дэниел; Раштон, Нельсон (2010), SequenceL: Transparency And Multi-Core Parallelisms (PDF) , DAMP '10 Материалы 5-го семинара ACM SIGPLAN по декларативным аспектам многоядерного программирования, Нью-Йорк, Нью-Йорк, США: ACM, стр. 45–52. , заархивировано из оригинала (PDF) 2 февраля 2017 г. , получено 26 января 2017 г.
^ Кук, Дэниел; Раштон, Нельсон (27–30 июня 2005 г.), «SequenceL - обзор простого языка», Материалы Международной конференции 2005 г. по языкам программирования и компиляторам, PLC 2005 г.
^ Строительные блоки Intel с резьбой (TBB)

Внешние ссылки [ править ]

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

[2] «Доктор Дэниел Кук из Texas Multicore Technologies» . Архивировано из оригинала 4 марта 2016 г. Проверено 24 февраля 2016 г.

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

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

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

[6] Банатер, JP; Ле Метайер, Д. (январь 1993 г.), «Программирование путем преобразования мультимножеств» (PDF) , Communications of the ACM , 36 (1): 98–111, doi : 10.1145/151233.151242 , S2CID 17076396

[7] Блеллок, Гай (март 1996 г.), «Программирование параллельных алгоритмов», Communications of the ACM , 39 (3): 85–97, CiteSeerX 10.1.1.141.5884 , doi : 10.1145/227234.227246 , S2CID 12118850

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

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

[10] Кук, Дэниел; Раштон, Нельсон (январь 1993 г.), «Разработка итеративных и параллельных алгоритмов на основе языковых трассировок высокого уровня», ICCS'05 Proceedings of the 5th International Conference on Computational Science , vol. Часть III, стр. 891–894, doi : 10.1007/11428862_132 , ISBN. 978-3-540-26044-8

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

[12] Texas Multicore Technologies, Inc.

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

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

[15] Строительные блоки Intel с резьбой (TBB)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]