WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 | 4 |   ...   | 5 |

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

Одной из проблем вычислительных машин с архитектурой потока данных является проблема управления памятью совпадений, которая используется для определения готовности команд к выполнению и хранения операндов команд, не готовых к выполнению. Переполнение памяти совпадений в таких вычислительных машинах приводит к блокировке (deadlock) вычислительного процесса. Основной причиной переполнения памяти совпадений является то, что параллелизм программ во многих случаях оказывается настолько большим, что имеющегося объема памяти совпадений оказывается недостаточно для хранения всех операндов команд, не готовых к выполнению. В ряде известных проектов по созданию вычислительных машин с архитектурой потока данных (например, MIT Tagged-Token Dataflow Architecture и Manchester Data-Flow Machine) для преодоления данной проблемы применялось принудительное ограничение параллелизма программы. Чтобы уменьшить параллелизм программы, использовались различные ограничения, накладываемые на программу на этапе ее исполнения. Например, ограничивалось количество одновременно выполняемых процедур программы или количество одновременно выполняемых итераций циклов с целью исключить саму возможность переполнения памяти совпадений. Недостатком такого подхода являлось то, что параллелизм программы на этапе ее исполнения во многом зависит от входных данных и может варьироваться в широких пределах. Таким образом, чтобы исключить возможность переполнения памяти совпадений, приходилось накладывать на программу очень жесткие ограничения, которые существенно снижали эффективность ее исполнения.

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

Производительность можно повысить, выполняя определенные операции распределения ресурсов на аппаратном уровне.

Во второй главе диссертационной работы исследованы модель вычислений и архитектура ВСАРР, определены принципы функционирования программного комплекса системного сопровождения вычислений для ВСАРР.

Модель вычислений ВСАРР ВСАРР основана на гибридной модели вычислений, управляемых потоком данных, с динамически формируемым контекстом. Программу, написанную для выполнения на ВСАРР, можно представить в виде направленного графа потока данных. В узлах этого графа располагаются операторы – программы, предназначенные для обработки операндов, поступающих на входы узлов. Операторы могут быть простыми, то есть, выполнять над поступившими операндами одну операцию, или сложными – выполнять над поступившими операндами несколько операций. Дуги графа отражают зависимость операторов по данным.

Таким образом, основной структурной единицей потоковой программы является узел. С каждым узлом связана программа, которая называется программой узла. Выполнение потоковой программы представляет собой серию активаций программ узлов. Активация и выполнение программы узла происходит при поступлении на узел полного комплекта операндов. Как правило, в процессе вычислений программа узла активируется многократно.

Активированные программы узлов выполняются параллельно и независимо друг от друга. Программа узла может выполняться одновременно над несколькими разными комплектами операндов.

Основными единицами информации в ВСАРР являются токен и пара.

Токены являются носителями операндов. В основном, они предназначены для обмена информацией между узлами. Несколько полей токена объединяются в единую структурную единицу, называемую ключом токена. Ключ токена участвует в операции поиска в памяти совпадений для выявления парных токенов. При выявлении совпадающих по ключу токенов происходит их взаимодействие и формируется пара. Каждая пара включает в себя два операнда и адрес программы узла, обрабатывающей эти операнды. Таким образом, пара содержит комплект операндов, необходимый для активации программы узла.

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

Проблема переполнения памяти совпадений в ВСАРР решается за счет введения виртуальной памяти. Функционирование виртуальной памяти основано на том, что все множество токенов задачи может быть разбито программистом на набор независимых подмножеств – подзадач, каждое из которых гарантированно умещается в доступный объем памяти совпадений.

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

Архитектура ВСАРР ИУ... ИУ Коммутационная среда токенов и пар Модуль АП... Модуль АП Модуль Модуль...

ООЗУ ООЗУ Дисковый Дисковый...

накопитель накопитель ХостЦУУП машина Рисунок 1. Структурная схема ВСАРР Исполнительные устройства (ИУ) обрабатывают поступающие из коммутационной среды пары, выполняя соответствующие программы узлов.

Как правило, результатом выполнения программы узла является один или несколько токенов, которые программа узла генерирует при помощи специальных команд. Через коммутационную среду эти токены направляются на модули ассоциативной памяти.

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

Результатом операции сопоставления может являться генерация одной или нескольких пар, которые через коммутационную среду направляются на исполнительные устройства.

Коммутационная среда осуществляет доставку пар к исполнительным устройствам и доставку токенов к модулям ассоциативной памяти.

Общее оперативное запоминающее устройство (ООЗУ) и диски в основном предназначены для хранения токенов и пар, откачанных из модулей ассоциативной памяти и внутренних буферов коммутационной среды.

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

Хост-машина представляет собой обычный персональный компьютер или сервер. Она предназначена для выполнения интерфейсных функций – организации взаимодействия между ВСАРР и другими вычислительными системами, а также, может быть использована для выполнения компонентов системного программного обеспечения ВСАРР.

Принципиальной особенностью ВСАРР является то, что большинство низкоуровневых операций по выделению и освобождению ресурсов выполняется на аппаратном уровне. Так, пары, формируемые в модулях АП, поступают на те ИУ, которые являются наименее занятыми. Токены, генерируемые в ИУ, распределяются между модулями АП в соответствии со значением хэш-функции от определенных полей токена. Токен, поступивший в модуль АП, записывается в любую свободную ячейку памяти. Стирание токена из модуля АП заключается в сбросе бита присутствия токена в памяти. Такой подход позволяет практически полностью устранить накладные расходы на распределение ресурсов вычислительной системы между задачами и между различными «ветвями» вычислительного процесса внутри каждой отдельно взятой задачи.

Программный комплекс системного сопровождения вычислений для ВСАРР Системное программное обеспечение ВСАРР должно поддерживать многозадачный многопользовательский режим работы вычислительной системы, удаленный доступ к вычислительной системе, механизмы интеграции вычислительной системы в традиционную вычислительную среду и так далее.

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

Фактически, чтобы продуктивно использовать ВСАРР в составе традиционной вычислительной среды, достаточно разработать набор компонентов системного ПО, позволяющий совместно с операционной системой хост-машины обеспечить выполнение вышеперечисленных требований.

Компоненты системного программного обеспечения ВСАРР могут выполняться непосредственно на потоковой вычислительной машине, на хостмашине и на персональных компьютерах пользователей. Непосредственно на потоковой вычислительной машине обязана выполняться только часть системного ПО – обработчики нештатных ситуаций и различные библиотеки.

Остальные компоненты системного ПО могут выполняться на хост-машине;

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

ВСАРР Персональный Пользователь компьютер Потоковая Персональный Пользователь Хост-машина вычислительная компьютер машина Персональный Пользователь компьютер Рисунок 2. Схема доступа пользователей к ВСАРР Предполагается, что основной целью работы пользователей с ВСАРР является запуск прикладных потоковых программ, позволяющих за сравнительно небольшое время выполнять необходимые пользователям вычисления. Таким образом, весь набор компонентов системного ПО, необходимый для продуктивного использования ВСАРР в составе традиционной вычислительной среды, можно охарактеризовать как программный комплекс системного сопровождения вычислений для ВСАРР.

Данный программный комплекс должен предоставлять пользователям следующие основные возможности:

• Доступ к ВСАРР с помощью локальной или глобальной сети со своего персонального компьютера.

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

• Запуск потоковых программ на ВСАРР с определенными исходными данными и получение результатов вычислений.

Программный комплекс должен включать в себя три части:

• Резидентная часть – выполняется на потоковой вычислительной машине, включает в себя обработчики нештатных ситуаций и различные библиотеки.

• Операционная часть – выполняется на хост-машине, осуществляет обработку различных видов пользовательских запросов и контролирует использование ресурсов хост-машины и потоковой вычислительной машины.

• Клиентская часть – выполняется на персональном компьютере пользователя, организует взаимодействие между пользователем и операционной частью программного комплекса.

Потоковая программа в стадии выполнения представляет собой иерархически организованную группу задач, выполняющихся в общем окружении. Иерархия задач представляет собой дерево, построенное на основе отношения «родитель-ребенок». Корнем дерева является так называемая главная задача, которая запускается при вводе пользователем задания на выполнение потоковой программы. Главная задача может запускать дочерние задачи, те могут запускать свои дочерние задачи и так далее. Под окружением выполняющейся потоковой программы понимается совокупность различных системных параметров и таблиц. Поскольку каждая потоковая программа выполняется в собственном окружении, исключается возможность нарушения работы одной программы другой программой.

Управление задачами и памятью в ВСАРР

Работая в многозадачном многопользовательском режиме, программный комплекс системного сопровождения вычислений для ВСАРР должен осуществлять планирование задач, то есть, предоставлять задачам доступ к вычислительным ресурсам ВСАРР в соответствии с определенными правилами.

Существует большое количество различных стратегий планирования, среди которых наиболее общей и универсальной является стратегия планирования в соответствии с приоритетами. Приоритет – некоторое числовое значение, которое пользователь, программист, администратор и системное программное обеспечение могут присваивать задачам. К алгоритмам планирования задач в соответствии с приоритетами предъявляются следующие основные требования:

Распределение ресурсов в соответствии с приоритетами – чем выше приоритет задачи, тем больший объем вычислительных ресурсов системы должен поступать в распоряжение задачи.

Предсказуемость – задачи должны регулярно получать доступ к вычислительным ресурсам системы.

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

Важность выполнения тех или иных требований определяется типом вычислительной системы. Например, для систем реального времени и интерактивных систем чрезвычайно важным является требование предсказуемости, а для систем пакетной обработки – требование балансировки нагрузки.

Планирование задач в ВСАРР связано со следующими проблемами:

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

Pages:     | 1 || 3 | 4 |   ...   | 5 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»