ВВЕДЕНИЕ

В данной работе рассматриваются проблемы решения обыкновенных дифференциальных уравнений при помощи многопроцессорных систем, базирующихся на программируемых логических интегральных схемах (ПЛИС). Суть данной работы состоит в том, чтобы выбрать несколько видов обыкновенных дифференциальных уравнений и решить их на нескольких многопроцессорных системах (содержащих не более четырех процессоров), и впоследствии сравнить полученные результаты. Указанные многопроцессорные системы должны быть разработаны на каком-либо языке описания компьютерной аппараратуры и затем имплементированы с помощью FPGA-чипа (FPGA – fast programming gate array – англоязычный аналог термина ПЛИС).

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

Под результатами в данном случае подразумевается временные характеристики разрабатываемой вычислительной системы.  А точнее - временная сложность выполнения одних и тех же наборов алгоритмов решения обыкновенных дифференциальных уравнений.

Временная сложность – это основной параметр, как известно, характеризующий алгоритм; он определяется как число шагов, выполняемых алгоритмом в худшем случае, обычно рассматривается как функция размера задачи, представленной входными данными [1]. В данном случае под шагом будет подразумеваться не машинная команда, а тик синхросигнала разрабатываемой машины. Это обусловлено тем, что обмен данными между узлами вычислительной среды может быть реализован несколькими способами, в частности с помощью всего одной процессорной команды. В последнем случае важную роль играет длительность выполнения данной команды.

1      NoC-СИСТЕМЫ

1.1       Тенденции развития SoC-систем

С ростом объемов эквивалентных вентилей в SoC-системах (system-on-chip – компьютерная система в пределах одного чипа) возникла необходимость некоторой переоценки архитектурных особенностей и особенностей проектирования подобных систем.  И в качестве идеи для дальнейшего развития SoC-систем была предложена концепция компьютерной сети на одном чипе (network-on-chip - NoC) [2].

Система на чипе (SOC) объединяет несколько процессоров в одном кремниевом чипе. Современные СБИС характеризуются малым временем наибольшего спроса на рынке (т. е. когда рынок проявляет наибольший интерес к изделию), высокой сложностью и высокой эффективностью. Когда время наибольшего спроса на рынке является одним из основных критериев планирования работы над проектом, сложность структуры и качество продукта могут “пострадать”, что может привести к неконкурентоспособности проекта. Использование ядер (core’s), т. е. готовых модулей, является одним из способов уменьшения сложности разработки современных цифровых систем. Часто в качестве подобных ядер выступают технологические продукты, программное обеспечение и теоретические знания, защищаемые патентами как интеллектуальная собственность (intellectual propriety - IP). Таким образом цифровая схема может содержать некие готовые компоненты (ядра), которые реализуют сложные вычислительные функции. Следование стратегии использования готовых ядер и готовых наработок, являющихся запатентованной интеллектуальной собственностью (IP), очевидно, дает выигрыш с точки зрения критерия времени наибольшего спроса на рынке.

В будущем, SOC будут включать десятки или даже сотни элементарных процессоров. Согласно “International Technology Roadmap for Semiconductors” (“Международный технологический план развития индустрии полупроводников”) технологические объемы SoC будут достигать четырех миллиардов транзисторов в одном кристалле, рабочая частота SoC будет равняться 10 ГГц. Такие преимущества как увеличение качества разрабатываемых проектов, сокращения затрат на разработку микросхем, размеров самих микросхем и потребляемых ими мощностей, а так же уменьшения времени полного технологического цикла разработки одной микросхемы, очевидно, будет достигаться с помощью применения SoC-технологий. Но системы на одном чипе должны быть масштабируемыми из-за потребности большого числа коммутаций в пределах одной разрабатываемой SoC (соединений между процессорными элементами либо между SoC нижнего уровня). Но в то же время организовывать SoC, как набор процессорных элементов по функциональности приведенных к одному процессорному элементу с множеством функциональностей не эффективно (при подобной реализации будет потерян параллелизм уровня команд процессора - ПУКП).

SOC-системы будущего поколения должны преодолевать проблемы, обусловленные ограниченными каналами связи, соединяющими функциональные элементы одного чипа, а именно:

• проблемы физических ограничений, которые уменьшают вычислительные возможности функциональных элементов и замедляют скорости обмена информацией между функциональными элементами;

• проблемы ограничений, обусловленных пропускной способностью межэлементных каналов связи;

• проблемы неэффективных схем синхронизации;

• проблемы ограниченности пропускной способности стандартных протоколов обмена, при использовании их во время организации обменов между функциональными элементами SoC;

• проблема большой зависимости производительности SoC от внутренней задержки межэлементных каналов связи;

• проблема потребности в большем параллелизме вычислительных процессов по сравнению с параллелизмом в SoC, имеющимся на данный момент;

• проблема сокращения потребления энергии SoC.

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

NoC – новый вид эффективной организации коммуникаций в пределах SoC-проектов.

1.2 NoC-подход к организации микросетей

Если рассмотреть SoC (System-on-Chip) как микросеть, с группой связанных процессорных элементов внутри, то это позволит применять технологии и инструментальные средства, используемые для проектирования и обслуживания обычной сети, что может значительно облегчить разработку SoC. В Таблице 1.1 показана разница между микро- и классической сетью (глобальной либо локальной).

Сеть в одном чипе разрабатывалась, для того, чтобы решать будущие проблемы повышения производительности SoC-систем. Данные проблемы преодолеваются за счет того, что обеспечивается возможность централизованного управления сетью. Эта возможность позволяет согласовать многочисленные ресурсы сети и стандартизировать протоколы обменов между этими ресурсами. Другим существенным преимуществом такой сети является потенциал использования проектирование сети на основе используемых многократно IP-блоков (IP-core’s).

Специалисты в области SoC Бенини и Мичели предлагают использовать так называемую микропарадигму стека сети для адаптации сетевого стека протоколов для NoC. Это позволит специфицировать электрические, логические и функциональные схемы взаимодействия в сети. Каждый уровень в вертикальном стеке сети должен быть специализирован и оптимизирован на столько, на сколько того требует его область применения.

1.1 Топология соединений в NoC-сетях

Физический уровень определяет топологию соединений проводников. Сигнал должен передаваться без ошибок. Затраты энергии на передачу сигнала должны быть по возможности минимальными, но при этом они должны обеспечивать удовлетворительную работу всех протоколов верхних уровней.

Средние сети общего доступа: данный вид топологии наиболее часто применяется в SoC-системах, характерны самыми простыми структурами организации каналов обмена информацией. В данной топологии все сетевые устройства коммутации являются общими с точки зрения доступа по отношению к другим функциональным элементам SoC. Но только одно устройство может управлять сетью в момент времени. Этот тип топологии – неэффективный с точки зрения энергетических затрат и не поддающийся масштабируемости.

Рисунок 1.1 – NoC-сеть прямого доступа.

Гибридные сети: реализуются с помощью иерархических шин либо многоканальных переключателей. Данная архитектура сети предусматривает большую коммутирующую способность и малое время обменов информацией между узлами сети.

1.1 Управление микросетью

Протоколы определяют, как использовать ресурсы сети во время системных операций. Динамическое управление сетью распределяет ресурсы сети вовремя этих операций, стремясь обеспечить необходимуе вычислительную мощь всей сети.

Уровень передачи данных: физический уровень, при передаче информации через который существует вероятность потери информации. Протоколы канального уровня увеличивают надежность связи, обеспечивая ее минимально необходимый уровень, т.к. физический уровень не является достаточно надежным. Эти протоколы обеспечивают обнаружение ошибок и исправление их. Канальный уровень также регулирует размерность и количество пакетов данных исходя из соотношения “количество проверочной информации / вероятность возникновения ошибки”.

Сетевой уровень: этот уровень осуществляет контроль соединений между конечными узлами. Здесь коммутация близко связана с маршрутизацией. Направляющие алгоритмы отвечают за создание канала для передачи сообщения конечному адресату. Детерминированные алгоритмы отвечают за создание того же самого канала обмена, но с поправкой на то, что между точкой отправления сообщения и точкой получения существует периодичность обмена сообщениями (достаточно постоянный трафик). Для данного рода алгоритмов построения информационного канала актуальным является не только адресат, но и отправитель (в отличие направляющих алгоритмов). Адаптивные алгоритмы анализируют трафик сети в целом с целью “устранения узких мест”. Данный подход предпочтительнее для сетей с непостоянным трафиком и ненадежными информационными узлами.

Транспортный уровень: отвечает за анализ и сбор пакетов сетевого уровня в единое целое. Степень детализации при пакетировании является важным фактором при проектировании всей системы, потому что большинство алгоритмов управления – очень чувствительны к размеру пакета. Однако ограничения обусловленные размерами пакетов в NoC менее критичны, чем в классических сетях.

2      РЕШЕНИЕ ОБЫКНОВЕННЫХ ДИФФЕРЕНЦИАЛЬНЫХ УРАВНЕНИЙ

Несмотря на постоянное повышение производительности процессоров, большое количество задач (в частности, сложные системы обыкновенных дифференциальных уравнений) является невыполнимым для однопроцессорных машин, так как время их решения неприемлемо велико. Для их выполнения применяют многопроцессорные машины, при этом задача разделяется на подзадачи, решаемые отдельно на каждом процессоре системы, после чего результаты решения подзадач обрабатываются для получения общего результата всей решаемой задачи. Область задач, требующих распараллеливание процесса вычислений, очень велико и распространяется практически на все сферы научных исследований и растет с каждым годом [3].

Целью работы магистра является разработка программного-аппаратного средства для параллельного расчета систем обыкновенных дифференциальных уравнений, представленных в виде задачи Коши. Для исследования процесса параллельных вычислений системы обыкновенных дифференциальных уравнений воспользуемся схемой Эйлера для численного интегрирования систем ОДУ. Каждое из уравнений можно рассматривать как отдельный процесс расчета на одном шаге интегрирования. Предполагается схема расчета:

• Оптимизация правой части уравнения путем преобразования инфиксной формы записи в постфиксную (ПОЛИЗ).

• Расчет многоитерационного процесса путем распараллеливания на каждом шаге интегрирования.

  Требования для этой системы:

• решение системы ОДУ за время меньшее, чем при последовательном расчете;

• самостоятельное разбиение исходной системы уравнений на параллельные блоки, обеспечивающие минимальное время расчета;

• проведение анализ примерного времени параллельного расчета и времени последовательного расчета;

• разбивка системы уравнений на параллельные блоки;

• анализ времени параллельного расчета.

Актуальность применения параллельного расчета систем ОДУ в форме Коши состоит в том, чтобы время расчета системы было меньше, чем при последовательном расчете.

ВЫВОДЫ

Планируемая работа магистра нацелена на то, чтобы реализовать с помощью многопроцессорной сети NoC (network-on-chip) параллельный решатель дифференциальных уравнений.

NoC содержит в себе большой потенциал, как следующая ветвь развития СБИС. Также теория организации SoC на данный момент имеет целый ряд белых пятен – одно из них организация NoC, обладающей топологией, специализированной для решения обыкновенных дифференциальных уравнений.

Решение поставленной задачи организации подобной NoC может привести к получению аппаратного решателя ОДУ, который будет иметь прозрачную масштабируемую структуру - удобную для последующих модификаций и обладающую высокой вычислительной производительностью.

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ

1. Web-Site of Program Construction and Optimization Laboratory Institute of Informatics Systems SD RAS.  http://pco.iis.nsk.su/grapp2/html/ReqtypetNamevremenna^_slojnost8.htm

2. Maria Elisabete, Marques Duarte. Networks on Chip (NOC): Design Challenges. Departamento de Informática, Universidade do Minho. http://gec.di.uminho.pt/discip/minf/ac0203/ICCA03/41720_NOC.pdf.

3. Белых А. А. Проблемы последовательно-параллельного анализа задачи Коши. Електронный сборник работ студентов кафедры АСУ. http://asu.cs.nstu.ru/doklads.html.