Содержание к диссертации
Введение
1. Анализ процессов высокоскоростной обработки данных 12
1.1. Определение задач больших размерностей 12
1.2. Анализ эффективности решения задач больших размерностей на высокопроизводительных вычислительных системах с традиционной архитектурой 26
1.3. Анализ путей построения проблемно-ориентированного вычислителя для решения вычислительно трудоемких задач 39
1.4. Архитектура ПЛИС-систем 52
1.5. Принципы построения проблемно-ориентированного вычислителя для решения вычислительно трудоемких задач 63
1.6. Выводы 73
2. Методы организации параллельно-конвейерных вычислений на основе плис-технологии для решения расчетоемких задач 76
2.1. Конвейерная реализация трудновычислимых фрагментов задачи 77
2.2. Параллельно-конвейерная реализация условных операторов 97
2.3. Реализация рекуррентных выражений 106
2.4. Реализация параллельных вычислений синхронизируемых макроконвейером 124
2.5. Выводы 132
3. Средства организации параллельно-конвейерных вычислений на основе плис-технологии для решения вычислительно трудоемких задач 135
3.1. Методы организации параллельно-конвейерных вычислений в вычислительных системах на основе ПЛИС 135
3.2. Средства программирования вычислительных устройств, построенных на основе ПЛИС-технологии, сочетающих конвейерные и параллельные методы одновременной обработки информации 144
3.3. Реализация генетического алгоритма на вычислительном устройстве, построенном на основе ПЛИС-технологии при сочетании параллельной и конвейерной одновременной обработки информации. 151
3.4. Выводы 170
Заключение 172
Список использованных источников
- Анализ эффективности решения задач больших размерностей на высокопроизводительных вычислительных системах с традиционной архитектурой
- Принципы построения проблемно-ориентированного вычислителя для решения вычислительно трудоемких задач
- Параллельно-конвейерная реализация условных операторов
- Средства программирования вычислительных устройств, построенных на основе ПЛИС-технологии, сочетающих конвейерные и параллельные методы одновременной обработки информации
Введение к работе
Актуальность темы. Бурное развитие науки и технологии порождает адекватный, а во многих случаях, и опережающий рост размерности актуальных хозяйственных, оборонных и научных задач.
Для решения таких вычислительно сложных задач в разумные промежутки времени, в том числе, в режиме on-line часто необходимы сверхвысокопроизводительные системы. Повышение производительности вычислительных систем в последние десятилетия XX века и начале XXI века определялось, прежде всего, прогрессом в микроэлектронной технологии. В то же время известно, что ресурс повышения производительности за счет одновременного выполнения операций во много раз превышает аналогичный ресурс за счет развития микроэлектронной технологии.
Один из подходов к созданию высокопроизводительных систем известен это построение конвейерных специализированных вычислительных устройств. Структура таких вычислителей изоморфна информационной структуре алгоритма, что обеспечивает естественное распараллеливание вычислительных процессов и минимизацию доли накладного времени до времени заполнения структуры конвейера. В то же время не вызывает сомнения, что создание множества специализированных дорогостоящих устройств, эффективно решающих единственную задачу, экономически нецелесообразно. Кроме того, не каждая задача допускает эффективную конвейерную реализацию.
Другим традиционным путем является создание решающего поля с помощью объединения некоторого множества процессорных элементов. Даже при существенном увеличении темпов обмена, которое может дать размещение указанных процессоров в одном кристалле, неизбежны проблемы согласования межпроцессорного взаимодействия, особенно при несбалансированной загрузке процессоров.
Естественной мерой эффективности той или иной формы одновременных вычислений представляется удельная производительность, являющаяся отношением реальной производительности к затратам аппаратных ресурсов.
Для эффективной одновременной обработки необходимо создавать устройства нового типа, которые обеспечивали бы реализацию совместной обработки сложной функции группой вычислительных устройств, при этом накладное время не должно быть выше собственно времени вычислений.
В последние годы появились ПЛИС, которые дают пользователям возможность создавать новые вычислительные структуры, которые реализуют как параллельный, как и конвейерный тип одновременных вычислений.
В настоящее время не существует математических методов и программных средств, которые позволили бы совмещать для единого устройства конвейерные и параллельные методы одновременных вычислений.
Объект исследований. Объектом исследования являются методы и программные средства, позволяющие сочетать параллельные и конвейерные методы одновременной обработки информации.
Целью работы является сокращение времени решения расчетоемких задач за счет создания методов и программного обеспечения, позволяющих эффективно совмещать конвейерные и параллельные методы одновременных вычислений в одном устройстве, построенном на базе ПЛИС.
Методы исследований. При проведении исследований были использованы элементы теории вычислительных систем, теория графов, теория множеств. Экспериментальные исследования проведены на действующих образцах вычислительных систем, построенных на основе ПЛИС-технологии.
Научная задача, решаемая в диссертации, - это создание методов и программных средств, позволяющих сочетать в едином вычислительном устройстве параллельные и конвейерные методы одновременной обработки информации для повышения производительности систем при решении расчетоемких задач и, как следствие, снижение времени решения таких задач до допустимых или требуемых пределов.
Для достижения указанной цели должны быть решены следующие научные задачи.
Проведен анализ методов и моделей одновременных вычислений.
Разработаны методы оценки эффективности реализации параллельных и конвейерных вычислений.
Разработана методика организации гибридных одновременных вычислений, сочетающих параллельные и конвейерные вычисления в едином вычислительном устройстве.
Разработаны программные средства для поддержки гибридных одновременных вычислений, сочетающих параллельные и конвейерные вычисления в едином вычислительном устройстве.
Разработаны алгоритмы решения прикладных задач на основе гибридных одновременных вычислений, сочетающих параллельные и конвейерные вычисления в едином вычислительном устройстве.
Научная новизна работы состоит в том, что в ней разработаны:
Новые методы анализа и выбора рационального варианта одновременной обработки для фрагмента задачи, содержащего условные операторы. Эти методы отличаются от известных анализом вероятности выполнения ветви условного оператора.
Новые методы анализа и выбора рационального варианта одновременной формы обработки для фрагмента задачи, содержащего рекуррентные выражения. В отличие от известных предлагаемые методы допускают параллельную, конвейерную, макроконвейерную или параллельно-конвейерную организацию вычислений для рекуррентных вычислений.
Новая методика организации гибридных одновременных вычислений, которая в отличие от известных методик сочетает параллельные и конвейерные вычисления в едином вычислительном устройстве.
Практическая значимость. Использование созданных методов и программных средств позволяет повысить производительность при решении ряда вычислительно сложных задач в 1,5-2 раза.
Созданные программные средства позволяют в 1,3 раза сократить время создания гибридных программ, сочетающих параллельные и конвейерные вычисления в едином вычислительном устройстве.
Созданные методы и программные средства обеспечивают расширение класса решаемых задач.
Новые алгоритмы одновременной обработки позволяют повысить скорость преобразования информации для процедур, использующих генетические алгоритмы, в 2-3 раза.
Использование результатов работы. Теоретические и практические результаты диссертационной работы использованы при выполнении НИОКР "Фактор", "Начинка", "Радикал", "Прокол-Б1", выполняемыми ЗАО "Эврика" и ОАО "СКБ Топаз", а также при разработке специального программного обеспечения в войсковой части 26165. Кроме того, созданные программные средства были использованы при разработке и отладке программно-технических средств перегрузочной машины ядерного реактора, выполняемых в рамках ОКР "Контроль", что подтверждается соответствующими актами внедрения.
Апробация работы. Основные результаты работы докладывались и обсуждались на всероссийских и международных научно-технических конференциях:
- Научная международная школа "Высокопроизводительные
вычислительные системы (ВПВС-2004)", Москва-Ростов-на-Дону-Таганрог,
2004 г.;
-Всероссийская Научно-Техническая Конференция "Параллельные вычисления в задачах математической физики", Ростов-на-Дону, 2004 г.;
- Международная конференция "Интеллектуальные и многопроцессорные
системы-2004", Украина, пос. Кацивели, 2004 г.
8 Наиболее важными из публикаций являются:
Иванов А.И. Требования к проблемно-ориентированным комплексам, предназначенным для решения задач, обладающих высокой емкостной и временной сложностью // Высокопроизводительные вычислительные системы (ВПВС-2004). Материалы научной международной школы. - Таганрог: Изд-во ТРТУ, 2004.-С. 75-79.
Иванов А.И. О создании и применении проблемно-ориентированных комплексов, предназначенных для решения задач, обладающих высокой емкостной и временной сложностью // Искусственный интеллект. — Донецк: Наука і освіта, 2004. - Т 4. - С. 15-26.
Иванов А.И. Требования к проблемно-ориентированным комплексам, предназначенным для решения задач, обладающих высокой емкостной и временной сложностью // Искусственный интеллект. Интеллектуальные и многопроцессорные системы. Материалы международной научно-технической конференции. - Таганрог: Изд-во ТРТУ, 2004. -Т 1. - С. 101-106.
Иванов А.И., Коновальчик П.М., Левин И.И., Малеванчук А.Д. Модульно-наращиваемые многопроцессорные вычислительные системы для решения задач математической физики // Материалы Всероссийской Научно-Технической Конференции "Параллельные вычисления в задачах математической физики". - Ростов-на-Дону: Изд-во ЮГИНФО РГУ, 2004. -С. 77-83.
Иванов А.И., Коновальчик П.М., Левин И.И., Малеванчук А.Д. Многопроцессорная система, адаптируемая под структуру задач различных проблемных областей // Искусственный интеллект. Интеллектуальные и многопроцессорные системы. Материалы международной научно-технической конференции. - Таганрог: Изд-во ТРТУ, 2004. - Т 1. - С. 34-38.
Иванов А.И., Коновальчик П.М., Левин И.И., Малеванчук А.Д. Многопроцессорная система, адаптируемая под структуру задач различных проблемных областей // Высокопроизводительные вычислительные системы
9 (ВПВС-2004). Материалы научной международной школы. - Таганрог: Изд-во ТРТУ, 2004. - С. 44-49.
Иванов А.И., Коновальчик П.М., Левин И.И., Малеванчук А.Д. Многопроцессорная система, адаптируемая под информационную структуру задач различных классов // Искусственный интеллект. - Донецк: Наука і освіта, 2004.-Т 3.-С. 140-148.
Иванов А.И., Коновальчик П.М., Левин И.И., Малеванчук А.Д. Макрообъектная вычислительная система // Тематический выпуск "Интеллектуальные и многопроцессорные системы". Известия ТРТУ. -Таганрог: Изд-во ТРТУ, 2004. - С. 28-36.
9. Иванов А.И., Коновальчик П.М. Методы организации параллельно-конвейерных вычислений для решения расчетоемких задач // Информационные технологии. Москва, 2004. - № 12. - С. 38-43.
Из работ, выполненных в составе коллектива авторов, в диссертации использованы результаты, полученные автором лично.
Структура диссертации. Диссертация состоит из введения, трех глав, библиографического списка и приложений.
Положения, выдвигаемые на защиту:
сочетание конвейерных и параллельных (мультипроцедурных) методов организации одновременных вычислений в едином вычислительном устройстве, построенном на основе ПЛИС, позволяет в несколько раз сократить время решения расчетоемких задач, содержащих генератор потока данных и блоки формирования и проверки гипотезы;
методика организации смешанных одновременных вычислений, в отличие от известных методик, сочетающая параллельные и конвейерные вычисления в едином вычислительном устройстве;
программные средства поддержки смешанных одновременных вычислений;
эффективная с точки зрения повышения удельной производительности реализация генетического алгоритма на основе смешанных одновременных
10 вычислений. В отличие от известных предлагаемая реализация алгоритма обеспечивает сочетание параллельных и конвейерных вычислений в едином вычислительном устройстве.
Первая глава посвящена анализу процессов высокоскоростной обработки данных. В ней сформулированы определения вычислительно трудоемких задач, форм одновременного выполнения операций. Проведен анализ эффективности решения задач больших размерностей на высокопроизводительных вычислительных системах с традиционной архитектурой. Проведен анализ путей построения проблемно-ориентированного вычислителя для решения вычислительно трудоемких задач. Предложены принципы построения такого вычислителя на основе ПЛИС-технологии и принципы построения его программного обеспечения.
Во второй главе рассматриваются методы организации параллельно-конвейерных вычислений в вычислительных устройствах, построенных на основе ПЛИС-технологии, для решения расчетоемких задач. Вводятся понятия последовательного, параллельного, последовательно-конвейерного и конвейерного выполнения информационных графов. Проводится анализ эффективности форм одновременной обработки вычислительно трудоемких фрагментов задач с точки зрения максимизации удельной производительности. Рассмотрены представляющие наиболее серьезную проблему для конвейерной реализации типовые фрагменты задач, в частности, содержащие условные операторы, рекуррентные выражения и большие объемы информационно-незначимых пересылок информации.
В третьей главе рассматриваются средства организации параллельно-конвейерных вычислений на основе ПЛИС-технологии для решения вычислительно трудоемких задач. Предложены методы организации параллельно-конвейерных вычислений для гибридных вычислительных систем, созданных на основе ПЛИС-технологии. Разработаны средства программирования, сочетающие конвейерные и параллельные методы одновременной обработки информации, подразделяющиеся на средства
описания и средства исполнения одновременных вычислений для вычислительных устройств, построенных на основе ПЛИС-технологии.
Как пример предложенных методов разработана реализация генетического алгоритма, сочетающая конвейерную и параллельную обработку в одном устройстве и обеспечивающая более высокую удельную производительность по сравнению с известными решениями.
Таким образом, в диссертации формулируется и решается актуальная научная проблема разработки методов и средств создания эффективных гибридных параллельно-конвейерных программ для вычислительных систем, построенных на основе ПЛИС-технологии.
Внедрение полученных в диссертации результатов позволяет решить ряд задач, которые в силу своей высокой сложности ранее были вычислительно недоступны.
Результаты диссертации внедрены в войсковой части 26165 (г. Москва), ОАО "СКБ Топаз" (г. Москва), ЗАО "Эврика" (г. Санкт-Петербург) и НИИ МВС ТРТУ (г. Таганрог).
Анализ эффективности решения задач больших размерностей на высокопроизводительных вычислительных системах с традиционной архитектурой
Наибольший вклад в развитие вычислительных средств всегда вносили технологические решения, при этом основополагающей характеристикой поколения вычислительных систем являлась элементная база, так как переход на новую элементную базу хорошо коррелирует с новым уровнем показателей производительности и надежности вычислительных систем. Поэтому бурное развитие технологии СБИС, разработка все новых и новых поколений микропроцессоров несколько приостановили поиски принципиально новых архитектурных решений. В то же время становится очевидным, что чисто технологические решения во многих случаях не могут обеспечить требуемый уровень производительности при решении широкого класса задач, поэтому без кардинальной перестройки архитектурных принципов поддерживать интенсивные темпы развития средств вычислительной техники уже невозможно.
Даже по самым оптимистичным прогнозам рост тактовых частот современных и перспективных СБИС не может быть бесконечным. В то же время достигнутая степень интеграции позволяет строить параллельные системы, в которых число процессоров может достигать десятков тысяч. Однако в области исследования архитектуры процессоров и вычислительных систем наблюдается кризис. Накопленный при создании МВС задел уже в значительной мере использован в архитектуре микропроцессоров, а "силовой вариант" построения суперсистем за счет объединения тысяч стандартных микропроцессоров не всегда обеспечивает высокую эффективность при решении реальных задач. В области повышения производительности вычислительных систем представляется, что резерв чисто технологических решений ограничивается одним порядком. Технологический вызов, связанный с перспективой освоения кристаллов, содержащих от 100 млн. до 1 млрд. транзисторов, может быть принят и поддержан только за счет новых идей в области архитектуры, схемотехники, новых вычислительных методов, алгоритмических и программных моделей, т.е. необходим комплексный научный подход. По оценкам ряда экспертов, при уменьшении технологических норм число транзисторов на кристалле за период с 1999 по 2012 год увеличится в 70 раз, а тактовая частота - лишь в 2,5 раза. Повысить тактовую частоту можно только за счет применения принципа близкодействия и использования схем с самосинхронизацией. Освоение же массового параллелизма и новых архитектурных решений содержит резерв повышения производительности на несколько порядков, а для этого, в частности, необходимо эффективное использование как обеих форм одновременного выполнения операций, так и их рациональных сочетаний.
Цели создания персональных компьютеров, в которых в основном используются стандартные микропроцессоры, и высокопроизводительных многопроцессорных вычислительных систем (МВС) существенно различаются. Совместимость для МВС во многих случаях гораздо менее значима, чем производительность и эффективность программ. Поэтому требуются значительные усилия на поиск новых методов вычислений с учетом особенностей одновременного выполнения операций аппаратными средствами [14]. В свою очередь, новые методы вычислений могут способствовать созданию новых архитектур.
Таким образом, основными требованиями, предъявляемыми к МВС, являются: - обеспечение требуемого высокого уровня производительности при решении задач; - согласование производительности памяти с производительностью вычислительной части; - способность процессоров согласованно работать при непредсказуемых задержках данных от любого источника.
Многими авторами отмечается, что увеличение степени параллелизма вызывает увеличение числа логических схем, что сопровождается увеличением физических размеров, в результате чего возрастают задержки сигналов на межсоединениях [15, 16, 17, 18]. Этот фактор приводит либо к снижению тактовой частоты, либо к созданию дополнительных логических ступеней и, в результате, к потере производительности. В свою очередь, рост логических схем также приводит к росту потребляемой энергии и отводимого тепла, что вызывает необходимость использования сложной системы энергообеспечения и специальных помещений.
Другим фактором, влияющим на архитектуру высокопроизводительных вычислительных систем, является взаимозависимость архитектуры и применяемых при решении задач методов и алгоритмов [19, 5]. С одной стороны, архитектура МВС оказывает сильное влияние на все этапы решения задачи, включая ее формулировку, выбор метода решения, разработку алгоритма, выбор технологии программирования, создание, отладку и собственно выполнение. С другой стороны, архитектура МВС может быть изменена или специально разработана для решения некоторых задач. Этот фактор часто приводит к необходимости создания проблемно-ориентированных систем, с помощью которых может быть достигнута максимальная производительность для данного класса задач. Указанная взаимозависимость является стимулом для поиска алгоритмов, наилучшим образом соответствующих возможным формам одновременного выполнения операций на уровне аппаратуры.
Принципы построения проблемно-ориентированного вычислителя для решения вычислительно трудоемких задач
Для того чтобы решить задачу большой размерности за приемлемое время, необходимо получить ресурс роста производительности, и такой ресурс имеется. Представляется, что подобным ресурсом может стать отказ от распараллеливания по фиксированной сетке разрядов данных, реализуемых в практически всех без исключения процессорных устройствах. Если направить освободившийся ресурс на распараллеливание по данным или по операциям, то при решении рассматриваемых в данной работе задач можно получить существенное увеличение производительности.
Надо помнить, что подавляющее число операций - в рассматриваемых задачах больших размерностей производится над логическими данными (в частности, битами или их некоторыми комбинациями), поэтому, создавая устройства обработки информации нового типа, можно получить рост производительности на два-три порядка выше по сравнению с реализацией задачи на универсальных микропроцессорах. Даже если созданные устройства будут иметь на порядок меньшую частоту, чем серийно выпускаемые микропроцессоры, то выигрыш в производительности все равно будет очень значительным.
Имеются и технические средства для построения таких устройств -программируемые логические интегральные схемы (ПЛИС), в структуре которых могут быть реализованы специальные устройства, осуществляющие обработку фрагментов задач.
Известно, что максимальная скорость обработки информации может быть обеспечена в специализированном вычислителе, структурно реализующем решение задачи. Однако даже несущественные изменения в задаче, изменение и, тем более, появление новых алгоритмов обработки информации требуют разработки и создания различных проблемно-ориентированных вычислителей, что приводит к значительному увеличению стоимости решения как отдельной прикладной задачи, так и всего комплекса решаемых задач [40].
В этой связи актуальными являются разработка и создание реконфигурируемых вычислительных систем, в рамках архитектуры которых программист мог бы синтезировать виртуальные параллельно-конвейерные вычислители, структура которых была бы адекватна информационной структуре задачи или ее фрагменту [41].
Синтез виртуальной проблемно-ориентированной архитектуры в рамках универсальной многопроцессорной системы осуществляется путем соответствующей настройки компонентов системы: процессоров на выполнение определенных арифметико-логических операций, контроллеров распределенной памяти - на определенные процедуры обращений к каналам распределенной памяти, коммутаторов - на определенные коммутационные структуры, обеспечивающие пространственное соединение между собой множества процессоров и каналов распределенной памяти в соответствии с информационным графом задачи [42].
В то же время наиболее производительной будет система, архитектура которой будет адаптирована к структуре решаемой задачи на уровне логических элементов, однако такой подход потребует чрезвычайно сложного управления и может привести к резкому увеличению времени перестройки системы с одной вычислительной структуры на другую.
За последнее десятилетие сформировалось мнение, что комбинация микропроцессор/программные средства служит основой гибкости и функциональности и лишь в некоторых случаях обеспечивает решение проблемы быстродействия, в то время как аппаратные средства обеспечивают необходимое быстродействие при функциональной неизменности [44]. В тоже время, согласно принципу дуальности аппаратно-программной реализации вычислений [45, 4], любая вычислительная компонента может быть выполнена как программно, так и аппаратно. Появившиеся в последние годы системы с реконфигурируемой структурой подтверждают данную гипотезу.
Появление программируемых логических интегральных схем (ПЛИС) не изменило ситуацию: устройства, построенные с применением микропроцессоров, называют универсальными, а устройства, использующие аппаратные ускорения, - специализированными или проблемно-ориентированными. Даже комплексные системы, которые содержат как микропроцессоры, так и ПЛИС, не выделены в отдельный класс. Такие устройства называют гибридными, различая даже в одной архитектуре две независимые подсистемы.
Такое разделение связано с не совсем корректной трактовкой, что программируемые логические устройства являются технологически удачной заменой специализированных устройств. Это справедливо, но только отчасти, ведь и микропроцессоры разрабатывались как замена специализированных устройств. Можно утверждать, что микропроцессоры и ПЛИС являются полуфабрикатами, оба класса устройств не могут функционировать без дополнительных информационных средств. Такую специфику микросхем принято называть программированием. Для макропроцессоров присуще программирование во времени, а для ПЛИС - программирование в пространстве [45]. В процессе работы процессор последовательно получает команды и в соответствии с каждой из них осуществляет преобразование информации. Усложнение алгоритма приводит к увеличению количества команд, возможно, даже к увеличению количества типов команд и времени обработки. Для ПЛИС алгоритм выполняется в единой структуре (максимально параллельно).
Усложнение алгоритма приводит к увеличению числа задействованных логических элементов и площади кристалла.
Микропроцессоры и ПЛИС можно рассматривать в качестве граничных элементов, реализующих алгоритмы в различных физических пространствах (временные и пространственные модели). Промежуточным решением, которое позволило бы объединить преимущества обоих методов обработки информации, является динамически перестраиваемые программируемые логические элементы, у которых должна существовать возможность динамически в процессе решения задачи заменять всю структуру устройства или ее часть.
Параллельно-конвейерная реализация условных операторов
Однако далеко не все фрагменты задачи могут быть эффективно реализованы в конвейерной форме. Существует ряд типовых информационных структур, которые более эффективно реализуются параллельно в виде множества независимых процессов.
Прежде всего, это относится к условным операторам, встречающимся в трудоемких вычислительных фрагментах.
Условный оператор можно представить в следующем виде: if д then begin bj, b2,...., b„, end; (2.2) else begin cj, c2,...., cm, end; где a - логическое выражение; bj, b2,...., b„- группа операторов, которые выполняются, если а истинно; С], c2i...., ст - группа операторов, которые выполняются, если а ложно. Для простоты рассуждения положим, что операторы, входящие в группы b],b2, bn и с/,с2,....,ст, являются операторами присваивания и, как будет показано ниже, это не нарушает общности. Оператор присваивания может быть записан в виде где di - идентификатор / -го операнда; /- функция преобразования операндов.
Если оператор присваивания содержит в списке операндов функции / идентификатор результата, то такой оператор является рекурсивным.
Поскольку трудоемкий фрагмент вычислений представляется в виде информационного графа, в котором все циклические участки итерируются з пространстве [11], то можно предположить, что рекурсивных операторов в трудоемких вычислительных фрагментах не будет. Неслучайно в системах потоков данных действует правило единственной подстановки, которое требует, чтобы переменная в программе получала значение один раз [8].
Более строго оператор присваивания, реализующий конвейерную обработку, можно записать следующим образом:
Здесь d/ - значение /-го операнда ву -й момент времени.
Обобщенный условный оператор (2.1) может быть преобразован в следующую последовательность эквивалентных условных операторов [54]. А=а; if A then bi else с\\ if A then b2 else с?, if A then bk else Ck\
Здесь и далее A - идентификатор логической переменной. Таким образом, необходимо рассмотреть реализацию простого условного оператора.
Определение 2.4. Если в результате выполнения обеих альтернативных ветвей условного оператора происходит присваивание одной и той же переменной, то такой условный оператор называется полным условным оператором.
Пример полного условного оператора представлен ниже. if a then di=fT(d,,d2,...,dk); else d, =feT(d„d2,...,dk); Здесь и далее fT - функция, соответствующая вычислениям по ветке then, fE - функция, соответствующая вычислениям по ветке else.
Такой оператор может быть естественным образом преобразован в оператор присваивания и далее в конвейерную форму, при этом ключевое слово if заменяется дизъюнкцией, ключевое слово else - конъюнкцией с инверсией логического выражения: d/ = a&fT(dJd{,...,d()va&fE(dJdi,...,dt). На рис. 2.13 представлена конвейерная форма полного условного оператора. л Рис.2.13. Конвейерная форма полного условного оператора.
В то же время, если идентификатор левой части оператора присваивания входит только в одну группу then или else, это определяет условный оператор, в который входит указанный идентификатор как рекурсивный. Запись вида if a then d/ = A(d/,d/ d{)\ эквивалентна записи if a then dj = fx(d{,d{ d{) else d/ = d/-l\
Если в информационном ациклическом графе G имеется п изоморфных непересекающихся подграфов Gx,G2,...,Gn, причем каждый из подграфов содержит некоторый подграф U1,U2,...,Un, который соответственно является условным, в общем случае, вложенным оператором (группой условных вложенных операторов), то конвейерная реализация графа G G = »G{ 100 целесообразна при условии, если мощность множества операционных вершин дополнения подграфа U\ в изоморфном подграфе G\ больше мощности операционных вершин подграфа U; M0(Gi/Ui) M0(Ui). Здесь и далее MQ(G\) — мощность множества операционных вершин подграфа G\. В противном случае следует перейти к параллельно-последовательной реализации подграфов к п . л: . G = - c/, G,. = +c/. У=і«=і j=i
Более строго следует определить эффективность конвейерной реализации совокупности условных операторов и операторов присваивания подграфа Gx.
Если мы имеем дело с полным условным оператором, то эффективность (отношение реальной производительности системы к пиковой) конвейерной реализации можно оценить по следующей формуле [55]: Е_ РТП(/Т) + РЕП(/Е) + ПШ ; (2.3) n(fT) + n(fE) + n{a) + n(DY где n{g) - число операций, которые необходимо выполнить для вычисления функции g; РТ РЕ " вероятности срабатывания ветвей оператора; f(a) - предикат, определяющий, какая из веток условного оператора будет выполнена.
Здесь и далее n(D) определяет число дополнительных функциональных устройств, необходимых для реализации конвейерной формы условных операторов (два конъюнктора и дизъюнктор).
Если логические переменные вычислены предварительно и число операций в различных вариантах оператора присваивания пропорционально и достаточно велико, то эффективность конвейерной реализации полного условного оператора близка к 1/2. Таким образом, более половины оборудования конвейера используется неэффективно, поскольку реализует альтернативную ветку результата, которая, согласно полученному значению логического выражения а, не будет использована.
Средства программирования вычислительных устройств, построенных на основе ПЛИС-технологии, сочетающих конвейерные и параллельные методы одновременной обработки информации
Для реализации совместных параллельных и конвейерных вычислений разработаны и созданы специальные программные средства, которые подразделяются на средства описания и средства исполнения одновременных вычислений для вычислительных устройств, полученных на основе ПЛИС-технологии.
Структура средств описания одновременных вычислений представлена на рис. 3.9.
В состав данных средств входят: графический редактор описания фрагмента конвейерного вычисления, программа анализа синхронизации, программа оптимизации информационного графа конвейера, а также транслятор конвейерного графа в VHDL-описание [75].
Пользователь с помощью графического редактора создает конвейерный граф фрагмента вычислений. Скрин-шоты графического редактора приведены на рис. 3.10. После исправления синтаксических ошибок формируется корректный конвейерный граф, который поступает в программу ресинхронизации, в результате работы которой создается синхронизированный граф. Полученный граф проверяется с помощью программы моделирования. В результате исправления возможных ошибок формируется корректный синхронизированный граф, который с помощью конвертора преобразуется в VHDL-описание и может быть использован как самостоятельный элемент в практически любой среде проектирования ПЛИС.
Следует отметить, что в конвейерном графе можно использовать готовые элементы и блоки при условии наличия их функциональной модели, которая была бы воспринята средствами моделирования.
Пользователь может, в принципе, создавать конвейерный граф на языке VHDL или использовать среды проектирования ISE, Foundation и т.д.
Встраиваемая система, реализуемая на модулях ПЛИС, состоит из ядра операционной системы и решающего поля, логическая схема которой приведена на рис. 3.11. Здесь приняты следующие обозначения: Kj - модуль конвейерной обработки, Ц - процессор конвейера, Мк - модуль памяти, И5 -интерфейсный модуль. На решающем поле выполняются различные прикладные задачи в параллельно-конвейерной форме. В модулях конвейерной обработки вычисления выполняются структурно, в то время как процессоры конвейера выполняют процедурные фрагменты вычислений, а также организуют потоки данных между компонентами системы. Интерфейсные модули позволяют взаимодействовать различным компонентам решающего поля. Управление вычислительным процессом, загрузка и выгрузка исходных данных, а также программ процессоров решающего поля выполняется компонентами ядра встраиваемой операционной системы.
В ядро ОС встраиваемой системы входит менеджер запросов, загрузчик программ и менеджер процессов. Хост/Клиент Ядро ОС Менеджер запросов 1 —і Загрузчик —і— менеджер Решающее поле К2 — Кп — Иі "-Пі - -»- ГІ2" - и2 МІ - М Рис. 3.11. Структура встраиваемой системы.
Менеджер запросов обрабатывает и перенаправляет запросы между клиентскими процессами хост-машины и подсистемами ядра ОС, тем самым предоставляя клиентский программный интерфейс со стороны управляющей машины. Алгоритм работы менеджера запросов представлен на рис. 3.12.
Загрузчик выполняет функцию размещения исполняемого кода и статических данных прикладных программ в соответствующие сегменты памяти процессоров решающего поля.
Менеджер процессов обеспечивает выполнение программ процессоров решающего поля, позволяет реализовать режим отладки и тестирования.
На рис. 3.12 приведена укрупненная блок-схема алгоритма обработки клиентских сообщений менеджером запросов. Здесь Kj - код запроса, Oj - подпрограмма обработки К; запроса. Очередь запросов может быть реализована в виде кольцевого буфера с порядком обработки FIFO.
При интенсивном потоке запросов, кода среднее время поступления между запросами меньше среднего времени обработки в одном потоке, возможна многопоточная реализация процесса менеджера запросов. При этом обработка клиентских запросов выполняется асинхронно по мере их поступления. Синхронизация между рабочими потоками менеджера запросов достигается за счет введения общих объектов синхронизации доступа к очереди запросов. Также возможно введение атрибута следования в дескриптор запроса, который позволяет упорядоченно извлекать из очереди последовательность запросов.
Менеджер процессов осуществляет обмен сообщениями с процессами решающего поля и реализуется подобно менеджеру запросов. Применение многопоточной реализации [76] позволяет выполнять разделение ресурсов ядра встраиваемой системы как в пространстве, так и во времени, увеличение интенсивности взаимодействия с процессорами решающего поля возможно как за счет дополнительных устройств, так и за счет временного разделения имеющихся.
Обобщенный алгоритм функционирования рабочего потока менеджера процессов приведен на рис. 3.13.
При анализе состояния процессов рассматривается значение слова статуса каждого процесса Со-Сп. Данные значения делятся на 2 множества: значения, при которых необходимо передавать сообщение о состоянии процесса host-машине, и значения, при которых необходимости в передаче нет. К первому множеству значений статуса относятся прерывания, исключительные ситуации, сбои и выходы из строя. Ко второму множеству относятся такие события как достижение локальных результатов программы, логические переходы в программе, информационные события.
