УСТРОЙСТВО ДЛЯ МУЛЬТИПРОГРАММИРОВАНИЯ КОНВЕЙЕРНЫХ СИСТЕМ Российский патент 1999 года по МПК G06F7/00 G06F17/00 G06F15/16 

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

В настоящее время известны устройства и методы для организации решения самых различных задач на конвейерных системах в мультипрограммном режиме. Производительность (длительность технологических процессов) последних напрямую зависит от близости полученных расписаний (порядка загрузки объектов в систему) к оптимальным [1, 2, 3, 4, 5]. Известно также [1, 2, 3], что если в конвейерной системе, состоящей из одной линии, число m станков (процессоров, автоматов и т.д.) больше или равно трем (m ≥ 3) и число N поступающих в эту систему объектов (например, для обработки деталей) достаточно большое (десятки, сотни, тысячи и т.д.), то поиск оптимальных расписаний считается бесперспективным, так как число их растет экспоненциально с ростом N и составляет N ! . Для этого применяют квазиоптимальные методы (см., например, с. 277 [1] и с. 244, 248 [3]) мультипрограммирования конвейерных систем. Известно также [1, 2, 3], что все существующие методы мультипрограммирования конвейерных систем основаны на применении ЭВМ, что требует как самой машины, так и составления для их работы программ. Причем при больших N для получения приемлемого расписания [1, 2, 3] необходимо или больше затрачивать машинного времени, или применять более мощную дорогостоящую вычислительную технику. Кроме того, необходимость использования программ для работа ЭВМ не позволяет оперативно получать расписания загрузки конвейерных систем, например, при обработке телеметрической информации, когда при смене режимов работы бортовой аппаратуры летательных аппаратов меняется количество N контролируемых параметров.

Все перечисленное выше ограничивает применение ЭВМ для решения самого широкого круга задач в народном хозяйстве и военном деле на системах конвейерного типа с максимальной их производительностью.

Наиболее близким к заявляемому изобретению по сущности решаемой задачи является "Устройство для вычисления дизъюнктивного логического определителя (патент N 2060537, кл. G 06 F 7/00, опубл. 20.05.96), которое без дополнительных существенных признаков не может самостоятельно решать задачу мультипрограммирования конвейерных систем.

Целью изобретения является расширение функциональных возможностей устройства.

Указанный технический результат достигается тем, что в устройство для мультипрограммирования конвейерных систем, состоящее из первого блока памяти, блока вывода, выход которого соединен с выходом устройства, блока вычисления функции A^v и блока ввода, содержащего m n-разрядных параллельных регистров (где m - число строк дизъюнктивного логического определителя, n - разрядность вводимых чисел), дополнительно введены генератор перестановок, блок выбора наименьшего результата, второй блок памяти, а в блок ввода дополнительно введены двоичный счетчик и (mn+r) буферных элементов (где r = log₂N, если log₂N - целое или округленное в сторону увеличения до целого число; N - количество столбцов дизъюнктивного логического определителя), первый вход каждого из mn буферных элементов соединен с одним из mn выходов параллельных регистров, при этом выходы буферных элементов объединены в m групп по n выходов в каждой и являются выходом данных блока ввода, первый вход каждого из остальных r буферных элементов соединен с одним из r выходов двоичного счетчика, выходы r буферных элементов при этом являются адресным выходом блока ввода, вторые входы всех буферных элементов соединены друг с другом, с тактовыми входами двоичного счетчика и параллельных регистров, с синхронизирующим входом устройства и с выходом РАЗРЕШЕНИЕ ЗАПИСИ блока ввода, информационные входы параллельных регистров соединены с информационными входами устройства, а входы установки в нуль этих регистров и двоичного счетчика - со входом НАЧАЛЬНАЯ УСТАНОВКА устройства, причем выход l-го разряда адресного выхода блока ввода (где l=1,..., r) соединен с выходом l-го разряда адресного выхода генератора перестановок и со входом l-го разряда адресных входов первого и второго блоков памяти, выход i-го разряда j-той группы выхода данных блока ввода (где i=1,...,n; j=1,...,m) соединен со входом i-го разряда j-той группы входа данных первого блока памяти, вход РАЗРЕШЕНИЕ ЗАПИСИ которого соединен с одноименным выходом блока ввода, а выход i-го разряда j-той группы выхода данных этого блока памяти соединен со входом i-го разряда j-той группы входа данных блока вычисления функции A^v, вход ЗАПУСК ОТ ВНЕШНЕГО УСТРОЙСТВА которого соединен с выходом СЧИТЫВАНИЕ генератора перестановок и с входом СЧИТЫВАНИЕ второго блока памяти, а выход ЗАПРОС ДАННЫХ соединен со входом ЗАПУСК генератора перестановок, вход НАЧАЛЬНАЯ УСТАНОВКА блока вычисления функции A^v соединен с одноименными входами устройства, блока ввода, генератора перестановок и блока выбора наименьшего результата, вход НАЧАЛЬНЫЙ ЗАПУСК блока вычисления функции A^v соединен с одноименным входом устройства, а выход i-го разряда выхода РЕЗУЛЬТАТА ВЫЧИСЛЕНИЯ этого блока соединен со входом i-го разряда информационного входа блока выбора наименьшего результата, первый выход которого соединен со входом ЗАПИСЬ второго блока памяти, а выход i-го разряда второго выхода блока выбора наименьшего результата соединен со входом i-го разряда входа НАИМЕНЬШЕГО РЕЗУЛЬТАТА второго блока памяти, выход l-го разряда выхода РАЗРЕШЕНИЕ ЗАПИСИ генератора перестановок соединен со входом l-го разряда входа РАЗРЕШЕНИЕ ЗАПИСИ второго блока памяти, выход l-го разряда d-й группы первого выхода этого блока памяти (где d=1,...,N) соединен со входом l-го разряда d-й группы первого входа блока вывода, а выход i-го разряда второго выхода второго блока памяти соединен со входом i-го разряда второго входа блока вывода, вход РАЗРЕШЕНИЕ ВЫВОДА которого соединен с одноименным входом устройства.

Сущность изобретения поясняется чертежами, где на фиг. 1 представлена блок-схема устройства, на фиг. 2 - блок ввода, на фиг. 3 - первый блок памяти, на фиг. 4 - блок вычисления функции A^v, на фиг. 5 - блок выбора наименьшего результата, на фиг. 6 - генератор перестановок, на фиг. 7 - генератор случайных чисел, на фиг. 8 - второй блок памяти, на фиг. 9 - временные диаграммы работы устройства, на фиг. 10 - конвейерная система (из m-процессоров, станков и т. д.) и матрица времен обработки каждого из N объектов на каждом из m-процессоров, станков и т.д.), на фиг. 11 - вариант поиска оптимального расписания (порядка загрузки объектов в конвейерную систему, при m=3 и N=3).

Устройство (см.фиг.1) содержит: блок 1 ввода, первый блок 2 памяти, блок 3 вычисления функции A^v, блок 4 выбора наименьшего результата, генератор 5 перестановок, второй блок 6 памяти, блок 7 вывода.

Блок 1 ввода (см. фиг. 2) состоит из m параллельных регистров, равных числу процессоров (станков и т.д.) в конвейерной системе (см. фиг. 10) двоичного счетчика и (mn+r) буферных элементов с тремя выходными состояниями. Параллельные регистры, двоичный счетчик и буферные элементы могут быть выполнены соответственно на микросхемах К155ИР1, К155ИЕ7 и К155ЛП10.

Первый блок 2 памяти (см. фиг. 3) состоит из N рабочих ячеек, разрядность каждой из которых - mn. Блок памяти предназначен для хранения данных о времени обработки N объектов на каждом из m-процессоров (станков). Данную память можно выполнить на микросхемах, например К155РУ5.

Блок 3 вычисления функции A^v подробно описан в [6]. Он изображен на фиг. 4, где добавлена связь блока вывода со входом "нач.уст.0" блока 3 (фиг. 1).

Его задачей является вычисление дизъюнктивных логических определителей.

Блок 4 выбора наименьшего результата (см. фиг. 5) предназначен для выбора наименьшего результата вычисления блоком 3 дизъюнктивного логического определителя.

Конструктивно он может быть выполнен на микросхемах серии К155 и одной микросхемы серии К555 (компаратор К555СП1).

Генератор 5 перестановок (см. фиг. 6) предназначен для формирования перестановок из N столбцов матрицы A (см. фиг. 10) по случайному закону. Для простоты, в качестве примера, на фиг. 6 генератор перестановок представлен для случая, когда N=5. Основой генератора 5 перестановок является генератор 8 случайных чисел, который в качестве примера взят из [7[ (стр. 145) и доработан для применения в данном устройстве. В генератор 5 перестановок входят линейка из N триггеров и двухвходовых схем И, которая служит для исключения повторения одних и тех же чисел в формируемых перестановках. Триггеры на выходе генератора 5 предназначены для запоминания чисел перестановки в виде адреса с последующей выдачей его в первый 2 и второй 6 блок памяти. Счетчик на выходе генератора 5 перестановок предназначен для подсчета членов перестановки, выходы которого соединены со входами схемы И таким образом, чтобы обеспечить после формирования перестановки из N членов установку линейки триггеров в единичное состояние. Генератор 5 перестановок может быть реализован на микросхемах серии К155.

Второй блок 6 памяти (см. фиг. 8) предназначен для хранения членов перестановки при ее формировании и хранении всей перестановки, если ей соответствующий дизъюнктивный логический определитель имеет наименьший результат. Первая указанная функция второго блока 6 памяти выполняется на первой линейке N параллельных регистров, а вторая функция - на второй аналогичной линейке. На фиг. 8 для простоты второй блок 6 памяти приведен для случая N= 5. Второй блок 6 памяти имеет еще один параллельный регистр для записи наименьшего результата. Данный блок может быть также реализован на микросхемах серии К155.

Блок 7 вывода может быть исполнен в виде линейки из (N+1) параллельных регистров серии К155ИР1 для выдачи перестановки и соответствующего ей результата дизъюнктивного логического определителя.

Работа устройства состоит из трех этапов.

1. Начальная установка схем блоков устройства в исходные состояния перед работой.

2. Ввод данных в устройство.

3. Поиск оптимального расписания загрузки в конвейерную систему (мультипрограммирование системы).

На первом этапе на вход устройства (фиг. 1) НАЧАЛЬНАЯ УСТАНОВКА подают импульс напряжения высокого логического уровня (см. эпюру 1 на фиг. 9), в результате чего в блоке 1 ввода параллельные регистры и двоичный счетчик устанавливаются в состояние "ЛОГ.0", в блоке 3 вычисления функции A^v схемы блока синхронизации и блока ввода устанавливаются также в состояние "ЛОГ.0", в блоке 4 выбора наименьшего результата триггер первоначально устанавливается в состояние "ЛОГ.1", а первый параллельный регистр в состояние "ЛОГ.0", затем после записи "ЛОГ.1" в первый (верхний на схеме) параллельный регистр состояние триггера меняется на противоположное, при этом второй параллельный (нижний на схеме) регистр также устанавливается в состояние "ЛОГ.1", а на выходе данного блока 4 устанавливается состояние "ЛОГ.0", так как условие A <B не выполняется. При поступлении импульса высокого логического уровня на вход генератора 5 перестановок (фиг. 6) состояние "ЛОГ.0" принимают: триггер, двоичный счетчик и двоичный счетчик (фиг. 7) генератора случайных чисел 8.

На втором этапе осуществляют ввод данных матрицы A (см. фиг. 10) в первый блок 2 памяти. Для этого на вход блока 1 ввода подают в параллельном коде значения элементов столбцов матрицы A и одновременно с ними синхроимпульсы ввода (см. эпюры 2, 3, 4 на фиг. 9). Записанная матрица A данных в первый блок 2 памяти хранится без изменения данных на этапе мультипрограммирования конвейерной системы, т.е. память работает только в режиме считывания.

Этап мультипрограммирования конвейерной системы начинается с момента подачи импульса высокого логического напряжения на вход устройства НАЧАЛЬНЫЙ ЗАПУСК. Этот импульс запускает в работу блок 3 вычисления функции A^v [6]. Этот блок (см. фиг. 9 [6]) формирует сигнал ЗАПРОС ДАННЫХ, запускает им генератора перестановок и останавливается. Генератор перестановок по случайному закону формирует адреса ячеек первого блока 2 памяти и одновременно с ними сигнал СЧИТЫВАНИЕ, который запускает блок 3 вычисления функции A^v и дает разрешение на считывание данных из первого блока 2 памяти. Одновременно с формированием перестановки и вычислением соответствующего ей дизъюнктивного логического определителя числа самой перестановки, представляющие адреса ячеек памяти, записываются в первую линейку параллельных регистров второго блока 6 памяти. Причем запись проводится в регистры по порядку: сверху вниз. После перебора генератором 5 перестановок всех адресов (т.е. после формирования перестановки) он останавливается, а блок 3 вычисления функции A^v выдает на блок 4 выбора наименьшего результата результат вычисления. При этом если дизъюнктивный логический определитель предыдущей перестановки был больше по величине, то текущий результат записывается в параллельный регистр второго 6 блока памяти и одновременно с ним проходит запись чисел текущей перестановки во вторую линейку параллельных регистров.

Время мультипрограммирования зависит в основном от числа N. Например, если N = 50, то количество перестановок будет 50 ! прибл. 3 • 10⁶⁴. При увеличении числа N время мультипрограммирования растет по экспоненте.

Поэтому подачу сигнала на вход устройства РАЗРЕШЕНИЕ ВЫВОДА для получения квазиоптимального (оптимального) порядка загрузки объектов в конвейерную систему осуществляет пользователь исходя из практических соображений (располагаемого времени, требований к близости результата к оптимальному).

На эпюрах 5, 6, 7 фиг. 9 представлена работа устройства на третьем этапе. На фиг. 11 представлен пример для N=3 и m=3. Видно, что вторая перестановка уже дает наименьшее (оптимальное) время обработки объектов на конвейерной системе.

Литература
1. Левин В.И. Структурно-логические методы исследования сложных систем с применением ЭВМ.-М: Гл. ред. физ.-мат.лит., 1987. 304 с.

2. Танаев В.С., Сотсков Ю.Н., Струсевич В.В. Теория расписаний. Многостадийные системы.-М: Наука, 1989. 328 с.

3. Исследование операций: В 2-х томах. Том 2. Модели и применения /Под ред. Моудера Дж., Элмаграби С.-М.: Мир, 1981. 677 с.

4. Пашкеев С. Д. Основы мультипрограммирования для специализированных вычислительных систем.-М: Сов. радио, 1972. 184 с.

5. Словарь по кибернетике /Под ред. Михалевича В.С.-К.: Гл. ред. УЭС, 1989.-752с.

6. Новиков А.Н. и др. Устройство для вычисления дизъюнктивного логического определителя. Патент N 2060537, опубл. 20.05.96 .

7. Бобнев М.П. Генерирование случайных сигналов.-М: Энергия, 1971.-240 с.

Изобретение относится к вычислительной технике и преимущественно может найти применение при автоматизированном составлении расписаний работы детерминированных систем конвейерного типа, широко используемых в настоящее время на производстве, транспорте, учебном процессе, военной области, науке, например статистическом моделировании (по методу Монте-Карло), и в других областях, где технологические процессы представляют собой конвейерные системы. Техническим результатом является мультипрограммирование конвейерных систем и получение квазиоптимальных (оптимальных) результатов моделирования с наименьшими вычислительными затратами. Устройство содержит генератор перестановок, два блока памяти, блоки ввода и вывода, блок вычисления функций А^v, блок выбора наименьшего результата. 11 ил.

Устройство для мультипрограммирования конвейерных систем, содержащее первый блок памяти, блок вывода, выход которого соединен с выходом устройства, блок вычисления функции A^V и блок ввода, содержащего mn-разрядных параллельных регистров (где m - число строк дизъюнктивного логического определителя, n - разрядность вводимых чисел), отличающееся тем, что в него дополнительно введены генератор перестановок, блок выбора наименьшего результата, второй блок памяти, а в блок ввода дополнительно введены двоичный счетчик и (mn + r) буферных элементов (где r = log₂N, если log₂N - целое или округленное в сторону увеличения до целого число, N - количество столбцов дизъюнктивного логического определителя), первый вход каждого mn буферных элементов соединен с одним из mn выходов параллельных регистров, при этом выходы буферных элементов объединены в m групп до n выходов в каждой и являются выходом данных блока ввода, первый вход каждого из остальных r буферных элементов соединен с одним из r выходов двоичного счетчика, выходы r буферных элементов при этом являются адресным выходом блока ввода, вторые входы всех буферных элементов соединены друг с другом, с тактовыми входами двоичного счетчика и параллельных регистров, с синхронизирующим входом устройства и с выходом РАЗРЕШЕНИЕ ЗАПИСИ блока ввода, информационные входы параллельных регистров соединены с информационными входами устройства, а входы установки в нуль этих регистров и двоичного счетчика - с входом НАЧАЛЬНАЯ УСТАНОВКА устройства, причем выход l-го разряда адресного выхода блока ввода (где l = 1, ..., r) соединен с выходом l-го разряда адресного выхода генератора переустановок и со входом l-го разряда адресных входов первого и второго блоков памяти, выход i-го разряда j-той группы выхода данных блока ввода (где i = 1, ..., n; j = 1, ..., m) соединен с входом i-го разряда j-той группы входа данных первого блока памяти, вход РАЗРЕШЕНИЕ ЗАПИСИ которого соединен с одноименным выходом блока ввода, а выход i-го разряда j-той группы выхода данных этого блока памяти соединен с входом i-го разряда j-той группы входа данных блока вычисления функции A^V, вход ЗАПУСК ОТ ВНЕШНЕГО УСТРОЙСТВА которого соединен с выходом СЧИТЫВАНИЕ генератора перестановок и с входом СЧИТЫВАНИЕ второго блока памяти, а выход ЗАПРОС ДАННЫХ соединен с входом ЗАПУСК генератора переустановок, вход НАЧАЛЬНАЯ УСТАНОВКА блока вычисления функции A^V соединен с одноименными входами устройства, блока ввода, генератора перестановок и блока выбора наименьшего результата, вход НАЧАЛЬНЫЙ ЗАПУСК блок вычисления функции A^V соединен с одноименным входом устройства, а выход i-го разряда выхода РЕЗУЛЬТАТА ВЫЧИСЛЕНИЯ этого блока соединен с входом i-го разряда информационного входа блока выбора наименьшего результата, первый выход которого соединен с входом ЗАПИСЬ второго блока памяти, а выход i-го разряда второго выхода блока выбора наименьшего результата соединен с входом i-го разряда входа НАИМЕНЬШЕГО РЕЗУЛЬТАТА второго блока памяти, выход l-го разряда выхода РАЗРЕШЕНИЕ ЗАПИСИ генератора перестановок соединен с входом l-го разряда входа РАЗРЕШЕНИЕ ЗАПИСИ второго блока памяти, выход l-го разряда d-й группы первого выхода этого блока памяти (где d = 1, ..., N) соединен с входом l-го разряда d-й группы первого входа блока вывода, а выход i-го разряда второго выхода второго блока памяти соединен с входом i-го разряда второго входа блока вывода, вход РАЗРЕШЕНИЕ ВЫВОДА которого соединен с одноименным входом устройства.