Проект Templet

Эта страница только для чтения. Вы можете посмотреть её исходный текст, но не можете его изменить. Сообщите администратору, если считаете, что это неправильно.
=====Elastic computing: A portable optimization framework for hybrid computers=====
====Реферат====
Системы высокопроизводительных вычислений более не могут полагаться только на увеличение тактовой частоты и количества вычислительных узлов для удовлетворения растущих запросов на вычисления в связи с ограничениями накладываемыми источниками питания и увеличивающейся стоимостью охлаждения. В качестве альтернативы в высокопроизводительные системы интегрируются многоядерные процессоры и гетерогенные ускорители, такие как GPU и FPGA. Однако использование настолько гетерогенных систем сильно ограничивает круг пользователей - до экспертов в данных устройствах из-за значительного увеличения сложности разработки приложений. Для обеспечения более прозрачного использования гибридных систем, мы вводим “гибкие вычисления”, которые является фреймворком оптимизации, используя который разработчики приложений вызывают специализированные “гибкие функции”, которые содержат базу знаний альтернатив реализации и стратегий распараллеливания. Для каждой гибкой функции множество инструментов оптимизаций анализируют множество возможных реализаций, которые позволяют производить динамическую и прозрачную оптимизацию по нескольким ресурсам и параметрам времени исполнения. В этой работе мы представляем технологии предоставления возможности гибкого вычисления и оцениваем эти технологии на четырех различных гибридных системах, включая Novo-G FPGA суперкомпьютер. Результаты включают детализированные тематические исследования использования гибкого вычисления для временных свёрток интервала и нахождения абсолютной разности изображений, ускорение которой достигло 206 раз.

====1. Введение====
В течение прошлых нескольких десятилетий сообщество высокопроизводительных вычислений (HPC) полагалось, в основном, на увеличение тактовой частоты и увеличение числа вычислительных узлов, для удовлетворения возрастающей потребности приложений в вычислительных ресурсах. Однако следовать этому подходу всё труднее в силу некоторых ограничений. Рост тактовой частоты замедлился из-за ограничений по потребляемой мощности и теплоотводу накладываемых интегральными схемами, и увеличение размера систем становится экономически неосуществимым из-за затрат на охлаждение и потребляемую энергию [19], которые становятся доминирующим фактором в общей стоимости владения [21]. Чтобы преодолеть эти ограничения, в системы HPC установилась тенденция к увеличению гетерогенности, всё больше интегрируясь со специализированными микропроцессорными ядрами [1,29,33], графическими ускорителями (GPUs) [39,67], и программируемыми логическими интегральными схемами (FPGAs) [10,21]. Такие гибридные системы имеют тенденцию обеспечивать лучшую энергоэффективность по сравнению с микропроцессорами общего назначения [63,71] специализация позволяет значительно уменьшить потребляемую мощность, а также увеличить производительность [14,25]. Хорошим примером является суперкомпьютер Novo-G [21], который использует 192 FPGAs в 24 вычислительных узлах и достигает производительности, сопоставимой с Roadrunner и Jaguar – двумя лучшими суперкомпьютерами для вычислительных приложений биологии [21], если считать их идеально масштабируемыми - с линейно растущей производительностью при увеличении вычислительных ядер [66]. Кроме того, типичные суперкомпьютеры, как правило, потребляют в среднем 1.32 мегаватт [65], тогда как Novo-G потребляет максимум 8 киловатт.

Хотя гибридные системы обеспечивают существенные преимущества по сравнению с традиционными системами HPC, эффективное использование таких систем в настоящее время ограничивается значительно увеличенной сложностью разработки приложений, которая приводит к неприемлемо низкой продуктивности [48]. В то время как параллельному программированию с недавнего времени уделяют много внимания, добавление гетерогенных ресурсов добавляет дополнительную сложность, которая ограничивает круг пользователей до экспертов по этим устройствам. Например, с системой FPGA, разработчики приложений часто должны быть экспертами в логическом проектировании, языках описания аппаратных средств и инструментах синтеза. Системы с GPU, несмотря на то, что обычно программируются на языках высокого уровня, разделяют подобные проблемы из-за определенных архитектурных особенностей, которые существенные влияют на производительность [50].

Многочисленные системы автоматизированного проектирования нацелены на  уменьшение сложности проектирования гибридных систем, скрывая детали низкого уровня, используя высокоуровневую компиляцию [9,22,28] и высокоуровневый синтез [26,31,42,61] объединенные с новым, специализированными языками высокого уровня [31,55]. Хотя эти, используемые ранее, подходы оказывали некоторое влияние на производительность, фундаментальное ограничение этих подходов - попытка преобразовать и оптимизировать единственную реализации, определенной кодом программы. Много предшествующих работ [23,64] показали, что у различных реализаций того же самого приложения производительность изменяется в широких пределах в зависимости от архитектуры. Например, проектировщик, реализующий функцию сортировки, может использовать сортировку слиянием или bitonic сортировку для FPGA, но алгоритм быстрой сортировки для микропроцессора. Кроме того, проблема выбора алгоритма возникает не только для устройств; различные алгоритмы работают более эффективно для различных объёмов входных данных [47], различного количества ресурсов [20], и потенциально любых других параметр времени исполнения. Хотя существующие инструменты могут выполнить преобразования, чтобы оптимизировать реализацию, эти преобразования не могут преобразовать между алгоритмами (например, из быстрой сортировки в сортировку слиянием), что часто требуется для эффективной реализации на каком-то конкретном устройстве или для нескольких устройств. Таким образом, даже с улучшенными компиляторами, инструментами синтеза и языками, эффективная разработка приложений для гибридных систем все еще потребует существенного усилий разработчиков, ограничивая круг пользователей до экспертов.

Чтобы обойти эти ограничения, мы предлагаем дополнительный подход оптимизации, называемый гибкими вычислением, который позволяет прозрачно и портируемо разрабатывать приложений для гибридных систем, также позволяя приложению адаптироваться к различным условиям во время выполнения. Гибкое вычисление - фреймворк оптимизации, который объединяет стандартный код программы – потенциально написанный на любом языке – со специализированными гибкими функциями и соответствующими инструментами оптимизации. Основное новшество гибких вычислений в гибких функциях, которые обеспечивают базу знаний альтернативных реализаций и стратегий распараллеливания данной функции. Когда приложение вызывает гибкую функцию, инструменты гибкого вычисления анализируют доступные устройства и ресурсы (например, ядра, GPUs, FPGAs) и текущие параметры времени исполнения (например, объём данных), и затем прозрачно выбирают из многочисленных, предварительно проанализированных, возможных реализаций. В примере с сортировкой разработчик приложения, использующий гибкое вычисление, просто вызвал бы гибкую функцию сортировки, не определяя, какую реализация должна быть использована, которую инструменты гибких вычислений распараллелили бы  по доступным ресурсам, выбирая подходящие реализации для каждого ресурса. Таким образом, без усилий или знания архитектуры, разработчик приложения в этом примере в состоянии выполнить реализацию сортировки, которая эффективно использует преимущества всех гетерогенных ресурсов системы. В то время как в предыдущих работах приводились такие оптимизации для определенных систем, приложений и языков, насколько нам известно, гибкие вычисления - первая техника, которая потенциально позволяет обеспечить прозрачную оптимизацию произвольных функций для любых условия времени исполнения на любой гибридной системе.

Работа организована следующим образом. В разделе 2 рассматриваются связанные работы. В разделе 3 проводится краткий обзор гибкого вычисления. Раздел 4 описывает гибкие функции. В разделах 5-7 обсуждаются инструменты для оценки реализаций, планирования оптимизации и выполнения гибких функции. Раздел 8 резюмирует ограничения гибких вычислений. Раздел 9 представляет результаты экспериментов.

====2. Похожие работы====
Приложения, использующие codesign расширения [23] имеют общие черты с гибкими вычислениями, позволяя разработчику указать несколько реализаций функции, что позволяет компилятору рассматривать несколько возможностей для программной и аппаратной реализации. Хотя этот подход позволяет достичь лучшей переносимости и эффективности, разработчики приложений должны были вручную определить множества реализаций и в какие реализации в каких случаях компилятор должен использовать. С гибкими вычислениями, для случаев, для которых соответствующая гибкая функция уже реализована, разработчик приложения не определяют деталей реализации, а просто вызывают гибкую функцию с эффективной реализацией этой функции, определенной автоматически инструментами гибких вычислений. Кроме того, гибкое вычисление может комбинировать и запуска параллельно имеющиеся реализации, получая новую реализацию во время исполнения.

Фреймворки разработки приложений и программное обеспечение среднего уровня для гетерогенных систем также имеет общие черты с гибкими вычислениями. OpenCPI [44] обеспечивает ПО среднего уровня, абстрагирует гетерогенные компоненты в приложениях, основанных на компонентах для улучшения портируемости и минимизации отрицательных эффектов замены компонентов программного обеспечения. StarPU [3] обеспечивает систему времени исполнения, которая позволяет разработчикам запускать и управлять выполнением множества гетерогенных задач. FUSE [34] создает слой абстракции, который прозрачно выбирает между гетерогенной и CPU реализацией задачи. Vforce [46] основан на VSIPL ++ и создает слой абстракции, который позволяет суперкомпьютерным приложениям поддерживать множество реконфигурируемых систем. В то время как в предшествующих работах упрощается портируемость и увеличивает прозрачность для разработчиков приложений для гетерогенных систем, они все выбирают единственную реализацию функции. Гибкие вычисления расширяют эту функциональность, выбирая из многочисленных реализаций, автоматически распределяя вычисления по множеству вычислительных устройств.

Многочисленные компиляторы сфокусировались на автоматической параллелизации [16,22,30] и адаптивных методах оптимизации [9,36], чтобы оптимизировать приложения для различных многопроцессорных архитектур. Для FPGAs инструменты синтеза высокого уровня [26,31,42] сосредоточились на переводе и оптимизации высокоуровневого кода в специализированные параллельные реализации схем. Для GPUs фреймворки, такие как CUDA [50], Brook [8], и OpenCL [35] обеспечивают расширенную версию языка C, который позволяет коду быть скомпилированным как для центрального процессора, так и для GPUs. Некоторое предшествующее решения позволяли компилировать код для нескольких типов устройств для определенных типов вычисления. PLASMA [53] полагается на промежуточное представление, которое разработчики могут использовать, чтобы определить SIMD вычисление, которое может быть скомпилировано для CPU, GPUs и FPGAs. Точно так же Accelerator [7] предоставляет C++ объект, который разработчики могут использовать, чтобы определить параллельные по данным операции, которые могут быть скомпилированы для CPU, GPUs и FPGAs. В то время как эти инструменты упростили переносимость реализаций между устройствами, их эффективность все еще существенно ограничена единственным алгоритмом, описанным в оригинальной спецификации. Гибкое вычисление в дополнении к этим инструментам, позволяя указывать несколько реализаций, написанных на любом языке и использующих любой алгоритм, чтобы прозрачно работать совместно для повышения эффективности.

Предсказание производительности, анализ и методы моделирования - широко изученные темы, которые разделяют подмножество целей преследуемых гибкими вычислениями. Существующие методы предсказания производительности часто используются, чтобы оценить применимость особой архитектуры для определенных приложений [4,27,56], помочь рассмотрению множества возможных реализаций [40] и верификации [37], помочь выделить узкие места [49,62], среди других. Хотя большинство предыдущих работ сосредотачивается на микропроцессорах, другие подходы фокусируются на предсказание производительности для FPGAs, используя аналитические методы [27] и методы моделирования [60]. Некоторые предыдущие работы также позволяют моделирование систем целиком и прототипирование [24]. Ptolemy [17] является инструментом, который поддерживает несколько вычислительных узлов и сложных иерархических проектов для прототипирования и моделирования. Хотя существующее методы предсказания производительности и моделирования похожи на гибкие вычислением в этом, они учитывают оценку реализации приложения, эти методы автоматически не рассматривают альтернативы реализации или выполнения, и поэтому оптимизация приложения все еще требует усилий со стороны разработчиков. Множество предыдущих работ сфокусированы на рассмотрении множества возможных реализаций, чтобы автоматизировать эту оптимизацию [18,45,54], но в тех подходах не рассматривают использование альтернативных алгоритмы, разделения работы и устройств для всех возможных устройств, объёмов данных и предположений использования. Гибкое вычисление не требует никакой ручной оптимизации и автоматически исследует различные пути выполнения приложения прежде, чем выберет лучшее.

Предыдущие работы над подстраивающимся программным обеспечением и разделением вычислений, разделяют общие черты с гибкими вычислениями. FFTW (Fastest Fourier Transform in the West) [20] является адаптивной реализацией FFT, который настраивает реализацию, составляя маленькие блоки функциональности, названной codelets, по-разному в зависимости от особой архитектуры. OSKI (Optimized Sparse Kernel Interface) [68] является подобной библиотекой автоматически настраиваемых ядер разреженных матриц. ATLAS [70] является пакетом программ линейной алгебры, которые способны к автоматической подстройке себя к различным архитектурам. SPIRAL [57] является подобным фреймворком, но исследует выбор алгоритма и реализации для оптимизации DSP преобразований. Такие подходы по существу являются ограниченной формой гибкого вычисления, определенного для архитектуры микропроцессора и использования, определенных для применения стратегий оптимизации. PetaBricks [2] состоит из языка и компилятора, который позволяет выбирать алгоритм, но ограничивает решения по распараллеливанию статическим выбором. Qilin [38] может динамически определить эффективное разделение работы по гетерогенным ресурсам, но предназначается для операций параллельных по данным. MapReduce - программная модель, которая позволяет автоматическое разделение интенсивного по данным вычисления по узлам в группе [13] или ресурсы в системе [59], однако это только применимо к вычислениям, которое представимы в структуре map-reduce. Гибкие вычисления стремятся обеспечить фреймворк, который позволяют любой функциональности быть оптимизированной для любой архитектуры, так же как поддерживает динамическую параллелизацию работы по нескольким ресурсам. Кроме того, тогда как предыдущие работы сфокусированы, прежде всего, на гомогенной архитектуре, гибкие вычисления могут потенциально использоваться с любой многоядерной гетерогенной архитектурой, и может также приспособиться к изменениям во время исполнения.

Планирование распределения ресурсов подобно в цели гибкому вычислению. Многочисленные точные и эвристические алгоритмы [12] существуют для того, чтобы распланировать граф задач на заданный набор ресурсов. Некоторые предыдущие работы также приспособили эти алгоритмы для определенных типов устройств. SPARCS [52] планирует граф задач временно и пространственно на набор FPGAs. Quinn и др. [58] определяет, где какая стадия конвейера обработки изображения наиболее эффективна - на FPGA или на CPU. В то время как цель подобна, гибкие вычисления не ограничены статическим анализом неизменного пути выполнения. Вместо этого у гибких функций есть гибкость, чтобы обеспечить многочисленные реализации и альтернативы параллельного исполнения, благодаря которым фреймворк гибких вычислений добивается лучшей производительности.

Работа, представленная в этой статье, расширяет предшествующую работу над гибкими вычислениями [69]. Основные расширения включают в себя: улучшенный алгоритм оценки производительности реализации, более быстрая реализация механизма планирования для уменьшения накладных расходов на определение самой эффективной реализации гибкой функции и метод планирования распараллеливания, чтобы автоматически определить наиболее эффективный метод распределения вычислений гибкой функции по ресурсам.