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

Потоковая программа размещается в массиве ячеек команд (рис).

Схема работы процессора с управлением потоком данных

Команда наряду с кодом операции содержит поля, куда заносятся готовые операнды, и поле, содержащее адреса команд, в которые должен быть направлен в качестве операнда результат операции. Кроме того, каждой команде поставлен в соответствие двухразрядный тег (располагаемый в управляющем устройстве), разряды которого устанавливаются в «1» при занесении в тело команды соответствующих операндов. В состоянии тега «11» (оба операнда готовы) инициируется запрос к операционному коммутатору (ОК) на передачу готовой команды в соответствующее коду операции операционное устройство (ОУ).

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

Управление ресурсами вычислительных систем. Алгоритм SPT

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

При оперативной обработке вычислительных задач невозможно проводить одновременно и их сортировку. Задачи с различной длительностью решения поступают на процессор в случайном порядке. В связи с этим невозможно использовать режим SPT (Shortest-Processing-Task-first), назначающий задачи на решение в порядке убывания времени их решения.

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

Управление ресурсами вычислительных систем, алгоритм RR(Round-Robin)?

Алгоритм RR(Round-Robin - алгоритм циклического обслуживания).

Заявки на выполнение работ поступают с интенсивностью λ в очередь О, откуда они выбираются и исполняются процессором CPU. Для обслуживания отдельной заявки отводится постоянный квант времени q, достаточный для выполнения нескольких тысяч операций. Если работа была выполнена за время q, она покидает систему. В противном случае она вновь поступает в конец очереди и ожидает предоставления ей очередного кванта процессорного времени.

Управление ресурсами вычислительных систем, алгоритм Макнотона?

Рассмотрим систему с n идентичными процессорами, с помощью которой необходимо решить L независимых задач; каждая задача решается одним процессором в течение времени ti , где i = 1 , ., L. Требуется найти алгоритм, который для каждого данного пакета (набора) задач строил бы расписание решения задач на процессорах системы, обеспечивающее минимально возможное время решения. При этом достигается максимально возможная производительность системы.

Пример: в двухпроцессорной системе и при наборе задач с временем их решения 3; 3; 2; 2; 2 возможны различные варианты назначения задач на решение.

a) работает один процессор

b) работают два процессора

c) алгоритм Макнотона

Рис Варианты расписаний для двухпроцессорной системы

Минимальное общее время решения задач достигается в варианте в), для которого время решения пакета задач совпадает с соответствующим оптимальным значением T = Tопт = Q и в данном случае равно величине

Q = max {max ti, ()·∑ti}.

Величина Q является нижней границей для оптимального значения Tопт.

Длина любого расписания T ≥max ti — максимального из времен решения задач пакета, в то же время T ≥ (·∑ti) длины расписания в том случае, когда до момента завершения решения последней из задач пакета ни один процессор не простаивает, т.е. все процессоры имеют 100 %-ную загруженность.

В общем случае даже при n =2 задача поиска оптимального значения T очень сложная задача, т.к. все известные алгоритмы ее решения имеют трудоемкость, экспоненциально зависящую от L.

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

При этом считается, что после прерывания решение задачи может быть возобновлено с точки прерывания на любом процессоре, не обязательно на том, на котором задача решалась первоначально.

Число прерываний должно быть по возможности меньшим, так как с каждым актом прерывания связаны потери машинного времени на загрузку-выгрузку задач из оперативной памяти.

Рассмотрим алгоритм Макнотона построения оптимального по длине расписания с не более чем n-1 прерываниями.

Алгоритм Макнотона заключается в предварительном упорядочении задач по убыванию времени решения и назначении задач последовательно по порядку номеров одну за другой на процессоры системы справа налево от уровня Q.

Примем: n= 2, L = 4, время решения задач: 5; 4; 3; 2. (N задачи 1;2;3;4)

Тогда Q = max {5, ½ • (5 + 4 + 3 + 2)} = 7;

расписание, в соответствии с алгоритмом Макнотона, имеет вид, таблицы.