Содержание к диссертации
Введение
1. Методы и средства разработки структурных компонентов параллельно-конвейерных программ для реконфигурируемых вычислительных систем 21
1.1. Современные реконфигурируемые вычислительные системы. 23
1.2. Системы разработки схемотехнических решений прикладных задач на ПЛИС и РВС 32
1.3. Архитектура ПЛИС 41
1.4. Развитие наиболее перспективной системы разработки прикладных задач для РВС 47
1.5. Выводы 50
2. Метод топологической минимизации вычислительных структур прикладных задач 52
2.1. Информационный граф решения прикладной задачи на РВС 52 в виде логических функций 54
2.2. Существующие методы минимизации схемотехнических решений, представленных
2.3. Метод топологической минимизации вычислительной структуры.
2.3.1. Виды объединения элементов комбинационной схемы в группы, удовлетворяющие архитектуре базовых логических элементов кристалла ПЛИС 59
2.3.2. Минимизация вычислительной структуры при помощи таблицы истинности 61
2.3.3. Сокращение таблицы истинности 66
2.3.4. Минимизация логических функций с константами 68
2.3.5. Определение избыточности таблицы истинности 71
2.3.6. Процедура декомпозиции графа на подграфы 73
2.4. Экспериментальные исследования 79
2.4.1. Описание генератора комбинационных схем 79
2.4.2. Влияние характеристик комбинационной схемы на степень
сокращения используемых аппаратных ресурсов 82
2.4.3. Эффективность метода топологической минимизации 85
2.5. Выводы 88
3. Комплексная минимизация вычислительной структуры 89
3.1. Структурное решение прикладной задачи на РВС 90
3.2. Метод комплексной минимизации вычислительной структуры решения прикладной задачи на РВС 92
3.3. Конвейерные вычислительные структуры 94
3.4. Метод разделения триггеров на элементы памяти и синхронизации 98
3.5. Метод переноса триггеров синхронизации 102
3.6. Алгоритм, комплексной минимизации вычислительной структуры решения прикладной задачи
3.6.1. Алгоритм циклического анализа комбинационных схем 114
3.6.2. Алгоритм формирования списка «пограничных» элементов
3.7. Экспериментальные исследования 118
3.8. Выводы 123
4. Постпроцессор транслятора языка высокого уровня .. 125
4.1. Структура постпроцессора 126
4.2. Алгоритмы постпроцессора транслятора языка высокого уровня COLAMO. 130
4.2.1. Алгоритм синхронизации информационных потоков в информационном графе структурного решения прикладной задачи 130
4.2.2 Алгоритм минимизации системы синхронизации 140
4.3 Интеграция постпроцессора в систему разработки прикладных задач для реконфигурируемых вычислительных систем 143
4.4. Решение прикладных задач с использованием постпроцессора транслятора языка COLAMO 146 4.4.1 Реализация задачи движения водной среды в Азовском море 146
4.4.2 Реализация задачи фильтрации жидкости в пористой среде 154
4.5. Выводы 161
Заключение 163
Список использованных источников 165
Приложение 1. Задача движения водной среды в азовском море 176
Приложение 2. Задача фильтрации жидкости в пористой среде 204 приложение 3. Акты о внедрении результатов диссертационной работы 2
- Архитектура ПЛИС
- Виды объединения элементов комбинационной схемы в группы, удовлетворяющие архитектуре базовых логических элементов кристалла ПЛИС
- Метод комплексной минимизации вычислительной структуры решения прикладной задачи на РВС
- Алгоритм синхронизации информационных потоков в информационном графе структурного решения прикладной задачи
Введение к работе
Актуальность темы исследования. Реконфигурируемые вычислительные системы (РВС), построенные на основе программируемых логических интегральных схем (ПЛИС), в XXI веке получили новый импульс развития, что обусловлено их потенциально высокой реальной производительностью при решении прикладных задач различных предметных областей за счет адаптации архитектуры системы к вычислительной структуре решаемой задачи.
Достижения высокой реальной производительности РВС невозможно добиться без минимизации вычислительной структуры разрабатываемой прикладной задачи. Минимизация вычислительной структуры приводит к повышению важнейшего технического параметра прикладной задачи при решении на РВС – удельной производительности, - показывающего отношение реальной производительности системы к количеству используемого ресурса ПЛИС. Современные средства минимизации занимаемых ресурсов ПЛИС, используемые в САПР ведущих мировых производителей (Xilinx ISE, Vivado, Quartus и др.), ориентированы на сокращение вычислительной структуры в пределах одного кристалла ПЛИС. В настоящее время для РВС, состоящих из полей ПЛИС, характерны приложения, которые реализуются на сотнях кристаллов, поэтому существующие специализированные однокристальные САПР не могут быть эффективно использованы для минимизации многокристальной вычислительной структуры без её предварительной компоновки в набор однокристальных конфигурационных проектов ПЛИС. Существующие многокристальные синтезаторы схемотехнических решений (например Fire!Constructor), осуществляют автоматическую компоновку и синхронизацию вычислительной структуры, но не выполняют ее минимизацию. Проводимая в дальнейшем средствами САПР локальная минимизация ряда отдельных однокристальных проектов не оказывает существенного влияния на перераспределение вычислительной структуры по задействованным в решении прикладной задачи кристаллам ПЛИС и не приводит к увеличению реальной производительности всей РВС. Для эффективного использования ресурсов ПЛИС в многокристальных проектах необходимо минимизировать вычислительную структуру всей решаемой прикладной задачи перед ее компоновкой на отдельные однокристальные проекты.
Минимизация вычислительной структуры приводит к повышению удельной производительности и, как следствие, к увеличению реальной производительности многокристальных РВС за счет возможности дополнительного масштабирования задачи, т.е. реализации вычислительных структур на освободившемся в результате минимизации ресурсе ПЛИС.
Отображение неоптимизированного информационного графа вычислительной структуры на архитектуру РВС может привести к нерациональному использованию критических ресурсов вычислительной системы, к которым относятся каналы информационных обменов, базовые логические элементы (Look-Up-Table), внутренняя память и другие ресурсы, что приводит к значительному снижению реальной производительности системы.
Поэтому для рационального использования ресурсов РВС необходимо разработать методы, повышающие удельную производительность за счет минимизации вычислительной структуры прикладной задачи, и реализовать их в виде программного компонента, преобразующего параллельно-конвейерную программу –
постпроцессор транслятора системы программирования многокристальных РВС на основе ПЛИС.
Цель работы - повышение удельной производительности РВС при выполнении параллельно-конвейерных прикладных программ.
Объектом исследований являются методы и средства преобразования параллельно-конвейерных программ для РВС.
Предметом исследований является программный компонент - постпроцессор транслятора языка программирования высокого уровня для РВС.
Научная задача, решаемая в диссертационной работе, – разработка методов преобразования параллельных прикладных программ, минимизирующих используемый в ПЛИС РВС ресурс для решения прикладных задач при заданной тактовой частоте.
Для достижения сформулированной цели необходимо решить следующие задачи:
1) провести анализ методов и средств разработки и минимизации
вычислительных структур параллельно-конвейерных программ для РВС;
2) разработать методы минимизации вычислительной структуры прикладной
задачи на РВС;
3) разработать программный компонент (постпроцессор), реализующий
разработанные методы минимизации вычислительной структуры прикладной задачи с
учетом архитектурных особенностей целевой РВС;
4) провести экспериментальные исследования эффективности разработанных
методов при решении реальных прикладных задач на РВС.
Методы исследований. Для проведения исследований были использованы методы теории графов, теории множеств, структурного программирования, объектно-ориентированного программирования. Экспериментальные исследования проводились на реконфигурируемых вычислительных системах, построенных на основе семейств ПЛИС нескольких поколений.
Достоверность и обоснованность научных результатов, полученных в диссертационной работе, подтверждены актами внедрения в различных организациях, корректностью и непротиворечивостью математических и логических выкладок, а также экспериментальными исследованиями. Результаты диссертационного исследования докладывались и обсуждались на российских и международных научных конференциях и научных школах, где выступления соискателя с докладами по разрабатываемой им тематике получили положительный отзыв научной общественности.
Научная новизна диссертации заключается в том, что в ней разработаны:
-
модернизированный метод топологической минимизации вычислительной структуры прикладной задачи для РВС, отличающийся заменой группы связанных логических элементов базовым логическим элементом (LUT);
-
новый метод комплексной топологической минимизации конвейерной вычислительной структуры прикладной задачи для РВС, отличающийся переносом синхронизирующих триггеров через цепочку логических элементов для понижения связности комбинационных схем;
-
структура постпроцессора транслятора, отличающаяся наличием процедур: покрытия информационного графа схемотехническими решениями, синхронизации информационных потоков, переноса синхронизирующих триггеров, топологической минимизации комбинационных схем.
Положения, выдвигаемые на защиту:
-
метод топологической минимизации сокращает вычислительную структуру прикладной задачи для комбинационных схем, в которых среднее количество входов и выходов логических элементов находится в интервале от 3 до 4,5;
-
применение топологического метода минимизации совместно со стандартными средствами оптимизации и минимизации (такими как Xilinx ISE, Vivado и др.) не увеличивает результирующую вычислительную структуру прикладной задачи;
-
уменьшение связности фрагментов вычислительной структуры при обеспечении заданной длины критического пути, определяемой периодом тактовой частоты, достижимо переносом триггеров синхронизации из одной комбинационной схемы в другую комбинационную схему через цепочку логических элементов;
-
сокращение связности фрагментов вычислительной структуры при использовании топологического метода минимизации вычислительной структуры приводит к более существенному сокращению вычислительной структуры прикладной задачи на РВС по сравнению с применением метода топологической минимизации без сокращения связности фрагментов вычислительной структуры.
Результаты, выносимые на защиту:
-
модернизированный метод топологической минимизации вычислительной структуры прикладной задачи для РВС, отличающийся заменой группы связанных логических элементов базовым логическим элементом (LUT);
-
новый метод комплексной топологической минимизации конвейерной вычислительной структуры прикладной задачи для РВС, отличающийся переносом синхронизирующих триггеров через цепочку логических элементов для понижения связности комбинационных схем;
-
структура постпроцессора транслятора, отличающаяся наличием процедур: покрытия информационного графа схемотехническими решениями, синхронизации информационных потоков, разделения вычислительной структуры на фрагменты, разделения триггеров на элементы памяти и синхронизации, переноса триггеров, топологической минимизации комбинационных схем, минимизации системы синхронизации.
Практическая ценность работы.
На основании предложенных методов создан программный компонент -постпроцессор транслятора языка программирования высокого уровня для реконфигурируемых вычислительных систем. Применение постпроцессора позволяет сократить вычислительную структуру прикладной задачи до ее компоновки, что приводит к более рациональному использованию аппаратного ресурса РВС и, как следствие, позволяет реализовать дополнительные вычислительные структуры, что повышает реальную производительность РВС. Минимизация вычислительной структуры задачи осуществляется с использованием архитектурных особенностей кристаллов ПЛИС целевой РВС, что позволяет сократить использование аппаратных ресурсов (базовых логических элементов) и повысить удельную производительность на 5-10% для задач различных предметных областей. Реализация дополнительных вычислительных структур на освободившемся ресурсе ПЛИС приводит к повышению
реальной производительности РВС в среднем на 8-20% при решении прикладных задач.
Реализация и внедрение результатов работы. Результаты диссертационного исследования использовались при выполнении ряда НИОКР в Научно-исследовательском институте многопроцессорных вычислительных систем имени академика А.В. Каляева Южного федерального университета (НИИ МВС ЮФУ), в рамках которых разрабатывались принципы создания системного и прикладного программного обеспечения РВС различных конфигураций и архитектур, наиболее значительными из которых являются:
– «Создание семейства высокопроизводительных многопроцессорных вычислительных систем с динамически перестраиваемой архитектурой на основе реконфигурируемой элементной базы и их математического обеспечения для решения вычислительно трудоемких задач», выполняемой в рамках федеральной целевой программы «Исследования и разработки по приоритетным направлениям развития научно-технологического комплекса России на 2007-2012 годы», № гос. рег. 01.2.00705707, Таганрог, НИИ МВС ЮФУ, 2009 г.;
– «Разработка методов и инструментальных систем для анализа эффективности работы параллельных программ и суперкомпьютеров», отчет о НИР, № гос. рег. И110519102540, Таганрог, НИИ МВС ЮФУ, 2012 г.;
– «Разработка реконфигурируемой вычислительной системы РВС-7 и организация на ее основе производства реконфигурируемых вычислительных систем с производительностью до 1015 операций в секунду в одностоечном конструктиве 47U», отчет об ОКР, № гос. рег. 49-15/259, Таганрог, НИИ МВС ЮФУ, 2013 г.;
– «Разработка и исследование принципов построения программных средств для высокопроизводительных реконфигурируемых вычислительных комплексов», отчет о НИР, № гос. рег. 01201153442, Таганрог, НИИ МВС ЮФУ, 2013 г.;
– «Разработка и исследование методов синтеза прикладных программ для реконфигурируемых вычислительных систем на основе перспективных ПЛИС сверхвысокой степени интеграции», отчет о НИР, № гос. рег. 114061040060, Таганрог, НИИ МВС ЮФУ, 2014 г.;
– «Разработка и исследование технологии создания ресурсонезависимого прикладного программного обеспечения высокопроизводительных вычислительных систем гибридного типа», Отчет о НИР, № гос. рег. 140912-077192, Таганрог, НИИ МВС ЮФУ, 2014 г.
Созданные методы, алгоритмы и программные средства внедрены в следующих организациях: НИИ МВС ЮФУ, г. Таганрог, Южном научном центре Российской академии наук (ЮНЦ РАН), г. Ростов-на-Дону; в научно-производственном объединении «Союзнефтегазсервис», г. Москва.
Апробация работы. Основные результаты, представленные в диссертации, докладывались и обсуждались на всероссийских и международных научно-технических конференциях: VIII, X, XI ежегодных научных конференциях студентов и аспирантов базовых кафедр ЮНЦ РАН, Ростов-на-Дону; III-ей международной заочной научно-практической конференции «Академическая наука - проблемы и достижения», Москва; XII Всероссийском совещании по проблемам управления
(ВСПУ-2014); Первом Международном симпозиуме «Гибридные и синергетические интеллектуальные системы: теория и практика, г. Светлогорск; 2-ой Всероссийской научно-технической конференции «Суперкомпьютерные технологии (СКТ-2012)», Геленджик, 2012 г., Шестой всероссийской мультиконференции по проблемам управления (МКПУ-2013), Геленджик, 2013 г.; 3-й Всероссийской научно-технической конференции «Суперкомпьютерные технологии (СКТ-2014)», Геленджик, 2014 г.; 8-ой всероссийской мультиконференции по проблемам управления (МКПУ-2015), г. Геленджик, 2015 г.
Личный вклад автора заключается в разработке методов преобразования параллельных прикладных программ, минимизирующих задействованный в ПЛИС ресурс для решения прикладных задач при заданной тактовой частоте.
Публикации. Основные положения диссертации опубликованы в 15 научных печатных работах: из них 3 статьи, 2 статьи из которых опубликованы в ведущих рецензируемых научных журналах из перечня ВАК РФ, а также тезисы и материалы 12 докладов на российских и международных научно-технических конференциях. По теме диссертационного исследования было получено 2 свидетельства об официальной регистрации программ для ЭВМ. Результаты работы используются в 9 отчетах о НИОКР.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав, заключения, списка использованных источников из 96 наименований и трех приложений. Основная часть работы изложена на 201 странице и включает 75 рисунков.
Диссертация соответствует п. 8 («Модели и методы создания программ и программных систем для параллельной и распределенной обработки данных, языки и инструментальные средства параллельного программирования») паспорта специальности 05.13.11 «Математическое и программное обеспечение вычислительных машин, комплексов и компьютерных сетей», технические науки.
Архитектура ПЛИС
Одной из основных причин снижения удельной производительности высокопроизводительных вычислительных систем являются неэффективность разрабатываемых параллельных программ и несоответствие вычислительной структуры решаемой задачи архитектуре вычислительной системы [33]. Существенное влияние на реальную производительность вычислительной системы оказывает ее коммутационная система информационных связей между процессорами. Время, необходимое для чтения данных, располагающихся в соседнем процессоре, может быть в тысячу раз больше времени, необходимого для доступа к собственным данным. Кроме всего прочего, необходимо обеспечивать синхронизацию вычислительных процессов, которые выполняются в разных процессорах, что также увеличивает время, затрачиваемое на накладные расходы, необходимые для организации параллельного вычислительного процесса.
Адаптация архитектуры вычислительной системы к структуре решаемой прикладной задачи является наиболее перспективным способом достижения высокой реальной производительности в настоящее время.
Данный подход нашел свое отражение в концепции построения реконфигурируемых вычислительных систем (РВС) [34-35], которые позволяют программировать свою архитектуру, создавая специализированную вычислительную систему, архитектура которой адаптирована под вычислительную структуру решения прикладной задачи. Решение прикладной задачи представляется в виде информационного графа [36], который с помощью программных средств отображается на архитектуру РВС. Данный подход обеспечивает не только высокую реальную производительность РВС при решении задачи, но и почти линейное увеличение производительности вычислительной системы при увеличении аппаратного (вычислительного) ресурса ПЛИС.
Подавляющее большинство современных РВС строится на основе программируемых логических интегральных схем (ПЛИС) [37, 38] различных производителей. ПЛИС как элементная база находят широкое применение в качестве различного рода контроллеров в бытовой и контрольно-измерительной технике, в системах связи и других областях. Популярность ПЛИС обусловлена возможностью реконфигурации, что позволяет изменять логику обработки информации, модернизировать, добавлять и удалять функции только лишь изменением конфигурации ПЛИС без изменения конструкции всего изделия. Использование ПЛИС для создания вычислительных систем имеет хорошие перспективы и пока не приняло массового характера.
Реконфигурируемые вычислительные системы на основе ПЛИС по числу используемых для вычислений микросхем можно разделить на два больших непересекающихся класса: однокристальные и многокристальные РВС. Большинство производителей (компании Nallatech [39], Alpha Data [40], National Instruments [41] и др.) выпускают однокристальные РВС, которые сравнительно просты в изготовлении и программировании, но их аппаратный ресурс не позволяет решать прикладные задачи в полном объеме. Для многокристальных РВС, которые являются предметом рассмотрения в настоящей работе, характерно наличие 4-16 кристаллов ПЛИС, связанных друг с другом пространственной коммутационной системой на основе высокоскоростных интерфейсов передачи данных, что, с одной стороны существенно усложняет программирование и синхронизацию вычислений, а с другой – за счет увеличения аппаратного ресурса позволяет реализовывать практические прикладные задачи.
Научно-производственное объединение «Роста» [42], основанное в 1993 году, проводит исследования, разрабатывает и поставляет устройства и программное обеспечение для построения сложных высокотехнологичных систем сбора и обработки информации. Основным направлением деятельности компании является разработка реконфигурируемых вычислительных систем и устройств на базе ПЛИС. В настоящее время на базе ПЛИС фирмы Xilinx разработаны вычислительные модули RSP-529 и RC-47. Модуль RSP-529 является аппаратным ускорителем вычислений на базе двух ПЛИС Xilinx Virtex 6 с интерфейсом PCI Express x8 gen 2.
Модуль выполнен в формате XMC и имеет симметричную архитектуру. На нем установлены две ПЛИС Virtex-6 в корпусе FF1759 из диапазона LX (240/365/550)T или SX (315/475)T.
Вычислительная плата RC-47 с четырьмя ПЛИС Virtex-7, соединенными интерфейсом PCI Express, является третьим поколением устройств, разработанных НПО «Роста» и построенных с применением новейших мировых продуктов и стандартов. На рис. 1.1 показан внешний вид вычислительной платы RC-47.
Виды объединения элементов комбинационной схемы в группы, удовлетворяющие архитектуре базовых логических элементов кристалла ПЛИС
При переносе решения задачи с одного кристалла ПЛИС на другой кристалл может потребоваться модернизация полученной ранее комбинационной схемы в том случае, если параметры логических элементов в этих кристаллах отличаются. При этом таблицы истинности, заменяющие функциональные блоки, могут быть либо увеличены, либо уменьшены. Увеличение или уменьшение зависит от параметров логических элементов кристалла ПЛИС, на который нужно перенести схемотехническое решение. Если параметры логического элемента превосходят параметры ТИ, то можно путем объединения получить таблицу истинности большей размерности в соответствии с методом, описанным в п. 2.3.1. Если же параметры логического элемента не позволяют реализовать ТИ на одном логическом элементе, то такую ТИ необходимо разделить на несколько ТИ.
Сократить таблицу истинности на один входной операнд можно, разделив ее на две равные части (младшую и старшую). При этом «старший» параметр (операнд) служит для переключения между полученными таким образом таблицами истинности. На рис. 2.6-а приведен пример элемента, реализующего логическую функцию от n переменных. На рис. 2.6-б показано, как исходный элемент разделяется на два элемента, реализующих логические «полуфункции» исходного элемента, объединенных при помощи мультиплексора. N
Описанные действия позволяют сократить исходную ТИ в два раза, разделив ее между двумя элементами. Однако такое сокращение глубины ТИ требует использования дополнительного оборудования в виде аппаратного ресурса, необходимого для реализации мультиплексора.
Процедура представления элементарного функционального блока от n параметров на основе таблицы истинности в виде двух элементарных функциональных блоков с n-1 параметрами и одного мультиплексора состоит из следующих этапов.
1) Разделить таблицу истинности на две равные части - «младшую» и «старшую». В «младшей» части находятся все значения исходной таблицы истинности, которые принимает исходная логическая функция при значении старшего параметра, равным «0». В «старшей» части находятся все значения исходной таблицы истинности, которые принимает исходная логическая функция при значении старшего параметра, равным «1».
2) Создать логический элемент на основе таблицы истинности. В качестве параметров созданного логического элемента (функции) использовать n-1 параметр исходного логического элемента (функции). В качестве таблицы истинности использовать «младшую» часть таблицы истинности исходного функционального элемента.
3) Создать логический элемент на основе таблицы истинности. В качестве параметров созданного логического элемента (функции) использовать n-1 параметр исходного логического элемента (функции). В качестве таблицы истинности использовать «старшую» часть таблицы истинности исходного функционального элемента.
4) Добавить в вычислительную структуру двухходовой мультиплексор. Выходы созданных логических элементов использовать (подключить) в качестве информационных входов мультиплексора, а в качестве управления использовать старший параметр исходной логической функции.
Как известно, таблица истинности представляет собой последовательность значений функции, адрес которых формируется при помощи позиционного кода (2.2).
При графическом отображении общепринято отображать младшие адресные биты справа, а старшие – слева [65]. То есть в адресе xn+xn-1+ … +x2+x1 бит x1 имеет наименьший вес, а бит xn – наибольший вес.
При переходе от функциональной схемы разрабатываемого вычислительного устройства к комбинационной схеме в результате анализа часть информационных потоков превращается в константы. Как правило, это происходит при явном определении некоторых параметров вычислительного устройства.
При анализе комбинационной схемы необходимо проводить ее минимизацию [66], результатом которой является модифицированная функционально и информационно эквивалентная комбинационная схема, позволяющая учесть воздействие констант на логику работы. При этом константы могут быть как явными, так и неявными.
Явные константы – это константы, установленные разработчиком для настройки того или иного параметра, а также возникающие при переходе от функциональной схемы к комбинационной. Неявные константы – это таблицы истинности, все значения которой равны между собой [67].
Оптимизация явных констант подразумевает сокращение таблицы истинности элементарного функционального блока в два раза на каждую константу. Поясним, что это означает. Предположим, имеется ЭФБ с n входами. Соответственно глубина таблицы истинности такого элементарного функционального блока равна 2n. Если заменить параметр r (1 r n) константой, то очевидно, что ТИ элементарного функционального блока должна сократится в два раза, поскольку один из параметров перестает быть переменным.
Для сокращения ТИ необходимо создать новую ТИ, глубина которой в два раза меньше исходной, и записать в нее соответствующие значения из исходной таблицы истинности. Алгоритм синтеза сокращенной ТИ представлен на рис. 2.7.
Неявные константы появляются при вырождении таблицы истинности. ТИ, которая вырождается в константу, имеет одно и то же значение во всех ячейках: F(x) = const, x = 1,…,2n. При обнаружении функционального блока с вырожденной ТИ необходимо на все инцидентные связи, выходящие из данного элементарного функционального блока, поставить соответствующую константу, все инцидентные связи, входящие в данный ЭФБ удаляются, также удаляется и сам элементарный функциональный блок. Удаление ЭФБ из комбинационной схемы позволяет сократить аппаратные ресурсы ПЛИС, необходимые для реализации данного элементарного функционального блока.
Метод комплексной минимизации вычислительной структуры решения прикладной задачи на РВС
Перенести те функциональные элементы из КСi+1 в КСi, перенос которых, во-первых, не приведет к нарушению устойчивой работы при заданной тактовой частоте (3.6), а во-вторых, позволит повысить связность КСi. На данном этапе для каждого элемента из множества элементов, выбранных на этапе 3, проводится перенос регистров синхронизации таким образом, чтобы выбранный функциональный элемент перешел из КСi+1 в КСi. После чего необходимо произвести разделение КСi на части и рассчитать связность Si полученного разделения. Если полученная связность больше исходной, то изменения в структуре решения прикладной задачи принимаются, иначе производятся откат и переход к анализу следующего функционального элемента. После каждой успешной операции перемещения регистров синхронизации (приводящей к повышению связности) необходимо заново выполнять 3-й этап, на котором анализируются функциональные элементы из КСi+1.
Определить в КСi-1 множество функциональных элементов, которые могут быть перенесены в КСi (множество пограничных элементов). После того, как все возможные переносы, приводящие к повышению связности КСi, сделаны, необходимо в КСi-1 определить множество функциональных элементов, которые при помощи перемещения регистров синхронизации могут быть перенесены в КСi.
Перенести те функциональные элементы из КСi-1 в КСi, перенос которых, во-первых, не приведет к нарушению максимального количества элементов в цепи при заданной тактовой частоте (3.6), а во-вторых, позволит повысить сумму связностей Si-1+ Si. На данном этапе для каждого элемента из множества элементов, выбранных на этапе 5, проводится перенос регистров синхронизации таким образом, чтобы выбранный функциональный элемент перешел из КСi-1 в КСi. После чего необходимо произвести пересчет связности Si-1 и Si. Если полученная сумма связностей больше исходной суммы, то изменения в структуре решения прикладной задачи принимаются, иначе производится откат и переход к анализу следующего функционального элемента. После каждой успешной операции перемещения регистров синхронизации (приводящей к увеличению суммы связностей) необходимо заново выполнять 5-й этап, на котором анализируются функциональные элементы из КСц. Созданный метод переноса триггеров позволяет переносить регистры синхронизации, изменяя границу между смежными комбинационными схемами, что приводит к уменьшению суммарной связности комбинационных схем и, как следствие, к сокращению аппаратного ресурса необходимого для реализации задачи.
Модификация смежных комбинационных схем, приводящая к сокращению используемого аппаратного ресурса ПЛИС, является многокритериальной задачей. И поэтому она не может быть решена математически. Рассмотрим подробно, какие критерии влияют на модификацию смежных комбинационных схем. В качестве основного критерия оптимизации будем использовать сумму удельных связностей смежных комбинационных схем (КС и КС+i) Sum = Si +SM, (3-14) где Si - связность КС i, SM - связность КС i+i. Будем обозначать связность КС после модификации как Si , тогда связность КСi+i будем обозначать как S"i+1. Тогда сумма связности смежных комбинационных схем будет равна Sum = S\+S\+K (3.15) Модификация смежных комбинационных схем должна приводить к сокращению суммы связности, поэтому модификации, проводимые с комбинационными схемами, должны проводиться таким образом, чтобы было справедливо следующее неравенство Sum - Sum . Учитывая, что где кі-количество внутренних связей КСІ, pi - количество внешних связей КСi, Vi - количество элементов, выполняющих логические операции, в КСІ, Aki - приращение количества внутренних связей в КСІ после модификации, Ар І - приращение количества внешних связей КСІ после модификации, Avi -приращение количества элементов, выполняющих логические операции, в КСІ после модификации.
Как видно из формул (3.22) и (3.23), полученные уравнения зависят от множества критериев, что делает невозможным решить задачу математически. Помимо многочисленных критериев, влияющих на значение неравенства (3.23), существует так называемый критерий критического пути. Данный критерий позволяет оценить, приводит ли модификация смежных комбинационных схем к нарушению длины критического пути или нет.
Таким образом, необходимо производить модификацию смежных комбинационных схем программным способом, который является итерационным. На каждой итерации программного метода модификации смежных комбинационных схем нужно при помощи первичной оценки определить элементы, которые могут быть перенесены в смежную комбинационную схему, после чего для каждого такого элемента выполнить перенос и произвести расчет суммы связности смежных комбинационных схем. На основе полученных численных значений производится окончательный анализ, как именно нужно модифицировать смежные комбинационные схемы.
Модификация смежных комбинационных схем производится для того, чтобы понизить суммарную удельную связность данных комбинационных схем. Поскольку модификация подразумевает перенос триггеров из одной комбинационной схемы в другую, необходимо определить критерии, позволяющие производить такой перенос.
1) Это, прежде всего, элементы, которые могут быть перенесены в смежную комбинационную схему, и должны находиться на «границе» комбинационной схемы, т.е. должны быть связаны со смежной комбинационной схемой через триггер(-ы), разделяющий смежные комбинационные схемы.
2) Переносимый элемент не должен быть связан с триггером, выполняющим функцию памяти, с той стороны, куда выполняется перенос. На рис. 3.5-а показан фрагмент конвейерной схемы, где регистр синхронизации обозначен как RS, а триггер, выполняющий функцию памяти, обозначен как Р. Если со стороны переноса элемент связан с регистром синхронизации, то такой перенос допустим (рис. 3.5-а). Если же элемент со стороны переноса связан с триггером, выполняющим функцию элемента памяти, то такой перенос недопустим (рис. 3.5-б).
Алгоритм синхронизации информационных потоков в информационном графе структурного решения прикладной задачи
Другая задача, на которой проверялась эффективность постпроцессора транслятора языка программирования высокого уровня COLAMO, была задача фильтрации жидкости в пористой среде. Задача описывается математически при помощи дифференциальных уравнений, составляющих задачу фильтрации жидкости в пористой среде, которая решается при геофизическом исследовании скважин, а также для моделирования процесса их эксплуатации [87].
Большая часть нефти в настоящее время добывается с помощью вторичных методов, таких как вытеснение водой из пласта. При закачке воды в подземные горизонты возникает необходимость решения сложной задачи – расчета влияния закачиваемой воды на интенсивность выхода нефти. В Приложении 2 приведено подробное описание задачи упрощенной модели однофазной фильтрации жидкости в пористой среде.
При реализации данной задачи на РВС были выделены вычислительно трудоемкие фрагменты и организована параллельная обработка данных фрагментов на РВС. Производительность РВС при этом пропорциональна количеству одновременно реализованных (работающих параллельно) фрагментов на РВС. При решении задачи фильтрации жидкости в пористой среде таким выделенным фрагментом является реализация узлового процессора для одной итерации алгоритма [Приложение 2], выполняющего необходимые математические расчеты в заданной точке.
Для решения задачи фильтрации жидкости в пористой среде были использованы две реконфигурируемые вычислительные системы: вычислительный модуль «Алькор» и вычислительный модуль «Тайгета», состав и характеристики которых были приведены выше (см. рис. 4.11, 4.14). Для реализации одного узлового процессора задачи фильтрации жидкости в пористой среде на ПВМ «Алькор» необходимо задействовать 118795 триггеров и 124968 логических элементов. Таким образом, для реализации одного узлового процессора на ПВМ «Алькор» было использовано 10,7% триггеров и 11,3% логических элементов. Поскольку аппаратные затраты принято измерять по критическому (наиболее использованному) ресурсу, то можно говорить о том, что реализация одного узлового процессора задачи фильтрации жидкости в пористой среде на плате вычислительного модуля «Алькор» использует 11,3% аппаратных ресурсов ВМ. Таким образом, на аппаратном ресурсе платы вычислительного модуля «Алькор» можно реализовать восемь узловых процессоров алгоритма, при этом будет использовано 90,4% аппаратных ресурсов ПВМ. На рис. 4.17 приведены экранные формы, показывающие использование аппаратных ресурсов ПВМ «Алькор» при реализации одного и восьми узловых процессоров.
Аппаратные ресурсы ПЛИС, используемые для синтеза структурного решения а) использование аппаратных ресурсов при реализации вычислительной структуры одного узлового процессора (использовано 11,3% аппаратных ресурсов ПВМ); б) использование аппаратных ресурсов при реализации вычислительной структуры 8 узловых процессоров (использовано 90,4% аппаратных ресурсов ПВМ)
Применение постпроцессора позволило сократить количество аппаратных ресурсов ПВМ, необходимых для реализации узловых процессоров. В таблице 4.5 приведены численные значения, показывающие, как применение постпроцессора сокращает вычислительную структуру (выражается в количестве неиспользованного аппаратного ресурса ПЛИС) одного и восьми узловых процессоров.
Аппаратный ресурс, занимаемый одним узловым процессором (без применения постпроцессора) 118795 (10,7%) 124968 (11,3%) Аппаратный ресурс, занимаемый восемью узловыми процессорами (без применения постпроцессора) 954161 (86,3%) 1000282 (90,4%) Аппаратный ресурс, занимаемый одним узловым процессором (с оптимизацией) 112803 (10,2%) 114794 (10,4%) Аппаратный ресурс, занимаемый восемью узловыми процессорами (с оптимизацией) 906235 (81,9%) 919424 (83,1%) Сокращение вычислительной структуры, реализующей один узловой процессор 5992 10174 Сокращение вычислительной структуры, реализующей восемь узловых процессоров 47926 80858