Устройство для распределения ресурсов внешней памяти вычислительного комплекса

СОВХОЗ СОВЕТСНИ 1СОЦИАЛИСТ ИЧЕСНРЕСПУБЛИН 124296 Р 130 ОСУДАРСТВЕННЫПО ДЕЛАМ ИЗОБРЕ ОМИТЕТ СССР ЕНИЙ И ОТНРЫТИЙ(56) Авторское881722, кл. САвторское св1051527, кл. УСТРОЙСТВО ДЛЯ РАСПРЕДЕЛЕНИЯ РЕВ ВНЕШНЕЙ ПАМЯТИ ВЫЧИСЛИТЕЛЬНОГЕКСА ение относится к вычисхнике и может быть исв устройствах для распре деления ресурсов в вычислительныхкомплексах. Целью изобретения является сокращение времени поиска свободной внешней памяти, Устройство содержит группу блоков анализа свободныхучастков внешней памяти, блок регистров, блок элементов сравнения, блоквыбора минимального числа, группуэлементов И, блок элементов ИЛИ, элемент задержки, регистр, группу формирователей импульсов, группу элементовИЛИ-НЕ. Устройство аппаратно реализует алгоритм поиска наиболее подходящего по размерам для вычислительныхресурсов участка внешней памяти вычислительного комплекса, 2 ил,1242969 1Изобретение относится к цифровойвычислительной технике и может бытьиспользовано в устройствах для рас"пределения ресурсов в вычислительныхкомплексах,Целью изобретения является сокращение времени поиска свободных участков внешней памяти.На фиг. 1 представлена структурнаясхема устройства; на фиг. 2 - схемаблока выбора минимального числа.устройство содержит (фиг. 1) группу блоков 1 анализа свободных участков внешней памяти, первый 2 и второй 3 блоки регистров, блок 4 элементов сравнения, блок 5 выбора минимального числа, блок 6 элементов И,блок 7 элементов ИЛИ, блок 8 элементов ИЛИ, элемент 9 задержки, регистр1 О, блок 11 регистров, блок 12 элементов сравнения, блок 13 выбора минимального числа, группу 14 формирователей импульсов, группу 15 элеменгов ИЛИ-НЕ, группу 16 элементов И.Блок выбора минимального числа25содержит (фиг. 2) блок 17 регистров,блок 18 поразрядных узлов анализа,первую 19, вторую 20 и третью 21группы блоков элементов И, первый 22и второй 23 блоки элементов ИЛИ, блок24 триггеров, блок 25 элементов И-НЕ,третий блок 26 элементов ИЛИ, блок27 элементов И.Кроме того, устройство имеет вход28 задания размера требуемой памятиустройства (фиг. 1), вход 29 запускаустройства, группу входов 30 размерамаксимального свободного участка памяти устройства, группу входов 31размера свободных участков памятиустройства, группу входов 32 начального адреса и номера блока памяти,устройства, информационный выход 33устройства, выход 34 готовности устройства, группу 35 информационныхвходов блока выбора минимального числа (фиг. 2), группу 36 установочныхвходов блока выбора минимальногочисла, вход 37 запуска блока выбораминимального числа, вход 38 сбросаблока выбора минимального числа, выход 39 блока выбора минимальногочисла,Устройство обеспЕчивает аппаратную реализацию процедуры "Дай кусок"для .выделения необходимых участковсвободной внешней памяти в вычислительном комплексе, Сущность процедурызаключается в следующем. 2При поступлении запроса на кусоксвободной памяти требуемого размерапо грубой таблице (слово которой содержит размер максимальной дыры свободной области памяти) точной таблицы и адрес первой дыры в этой таблице) находится наиболее подходящаяточная таблица, т.е, такая, максимальная дыра в которой минимальнопревосходит требуемый размер. Приэтом имеется гарантия, что в найденной точной таблице имеется по крайнеймере одна подходящая дыра, Продолжение поиска ведут в найденной точнойтаблице, при этом снова выбирают наиболее точную дыру, В результате работы процедуры выдается начальный адрес наиболее подходящей дыры и номервнешнего устройства, на котором онарасположена,В исходном состоянии триггеры 24блоков 5 и 13 выбора минимальногочисла находятся. в нулевом состоянии.По входу 28 в регистр 10 поступает код требуемого размера дыры. Блок11 регистров обеспечивает хранениеинформации грубой таблицы, и 1.-й (.- 1, п 1) регистр 11 по 1-му входу 30заносится код размера максимальнойдыры 1.-й точной таблицы. Блок 2 регистров .-го блока 1 анализа свободных участков внешней памяти предназначен для хранения -й точной таблицы,.по 3-му (3 = 1, ш) входу 31 в1-й регистр 2 1.-го блока 1 заноситсякод размера 1-й дыры х-й точной таблицы, Блок 3 регистров -го блока1 служит для хранения кодов начальных адресов соответствующих дыр 1-йточной таблицы и номеров внешнихустройств, на которых они расположены, в -и регистр 3 блока 1 по 1-мувходу 32 заносится соответствующий .код начального адреса и номера внешнего устройства,При поступлении запроса на память-м элементом 12 сравнения проводитсясравнение содержимого регистра 10 и1-го регистра 11, Если код -го регистра 11 превышает или равен содер- .жимому регистра 10, то на выходе-го элемента 12 сравнения появляетсяимпульс, который по -му входу 36устанавливает и единичное состояние 1-й триггер 24 блока 13 выбораминимального числа.Содержимое х-го регистра 11 заносится в .-й регистр 1. Из числа регистров 11 выбирают те, содержимоез 1242 которых удовлетворяет требуемому запросу на память (превышает или равно ему). Блоком 13 выбора минимального числа определяется номер -го регистра 11, в котором хранится код разме 5 ра наиболее подходящей дыры из грубой таблицы. Производится это следующим образом.Импульс по входу 29 устройства и по входу 37 запускает блок 13 выбо 10 ра минимального числа. Блоком 13 проводится поразрядный анализ сравниваемых чисел (записанных в регистрах 17), Если в первом разряде чисел име. ется и "0" и "1" то через элементыУ15 И 19 и 20 блока 18 узлов анализа на элементы ИЛИ 22 и 26 поступают единичные сигналы. На выходе соответствующего элемента И-НЕ 25 формируется нулевой сигнал, которым закры 20 вается соответствующий элемент И 27. Через элементы И 19 и 21, относящиеся к тем регистрам 17, в первом разряде которых "0", единичный сигнал поступает на входы установки в нулевое состояние соответствующих тригге ров 24. Элементы И 19 и 20 соответствующих узлов 18 анализа закрываются и единичный сигнал будет только на выходе элемента ИЛИ 26. На выходе элемента И-НЕ 25 формируется единич 30 ныи сигнал, по которому открывается элемент И 27. Далее проводится анализ следующего разряда оставшихся сравниваемых чисел.Если в первом разряде сравниваемых 35 чисел содержатся только нули или только единицы, то на выходе соответствующего элемента И-НЕ 25 присутствует единичный сигнал, ко. торый открывает элемент И 27, Следо вательно, в этом случае сразу проводится анализ второго или последующих разрядов. После того, как все разряды сравниваемых чисел проанализированы, на выходе элемента И 27 фор мируется единичный уровень. При этом на выходе 39 хранится унитарный код номера регистра 11, содержащего минимальное число, удовлетворяющее запросу. Таких чисел может быть несколько, тогда несколько триггеров 24 будут в единичном состоянии,На выходе -го формирователя 14 импульсов появится импульс если х-й триггер 24 в единичном состоянии. Если несколько триггеров 24 в единичном состоянии, то из их числа выбирается триггер 24, соответствующий 969 4регистру 11 с наименьшим номером Проводится это с помощью элементов ИЛИ-НЕ 15 и И 16. В результате описанного этапа работы устройства проведен выбор наиболее подходящей точной таблицы, которой соответствует блок 1.С помощью -го блока 4 элементов сравнения, проводят выбор дыр х-й точной таблицы, удовлетворяющих запросу на память, 3-й элемент 4 сравнения вырабатывает импульс, если код 3-го регистра 2 превышает или равен содержимому регистра 10. Блоком 5 выбора минимального числа проводят выбор дыры -й точной таблицы, наи.более подходящей требуемому запросу на память, Проводится это при поступлении импульса запуска с выхода 1-го элемента И 16 на вход запуска блока 5;. В результате на 1-м выходе блока 5 появляется сигнал, разрешающий прохождение кода начального адреса 1-й дыры -й точной таблицы и номера внешнего устройства, на котором она расположена, из 3-го регистра 3 через 1-й блок элементов И 6, 1-й блок элементов ИЛИ 7, блок 8 элементов ИЛИ на выход 33 устройства. Одновременно с этим на выходе 34 устройства появляется импульс готовности, который свидетельствует об окончании работы устройства и обнуляет триггеры 24 блоков 5 и 13 выбора минимального числа.Таким образом, предлагаемое устройство выдает начальный адрес наиболее подходящей дыры и номер внешнего устройства, на котором она расположена,Формула изобретенияУстройство для распределения ресурсов внешней памяти вычислительного комплекса, содержащее блок регистров, блок элементов сравнения, блок элементов ИЛИ и регистр, причем выход блока регистров подключен к первому входу блока элементов сравнения, о т л и ч а ю щ е е с я тем, что, с целью сокращения времени поиска свободного участка внешней памяти, в него введены группа блоков анализа свободных участков внешней памяти, блок выбора минимального числа, элемент задержки, группа формирователей импульсов, группа элементов ИЛИ-НЕ, группа элементов И, причем каждый блок анализа свободных участков внеш 124296925 ней памяти содержит первый и второй блоки регистров, блок элементов сравнения, блок выбора минимального числа, блок элементов И, блок элементов ИЛИ, выход задания размера требуемой памяти устройства подключен к входу регистра, вЫход которого соединен с вторым входом блока элементов сравнения и с первыми информационными входами всех блоков анализа свободных участков внешней памяти группы, 1-й (1 = 1, ш) вход размера свободных участков внешней памяти группы входов устройства и 1-й:вход начального адреса и номера блока памяФ ти группы входов устройства подключены соответственно к второму и третьему информационным входам -го блока анализа свободных участков внешней памяти группы, вход запуска устройства подключен к входу запуска блока выбора минимального числа и к входу элемента задержки, выход которого подключен к входу сброса блока выбора минимального. числа, выходу готовности устройства и к входам запуска всех блоков анализа свободных участков внешней памяти группы, выход блока элементов сравнения подключен к группе установочных входов блока выбора минимального числа, группа информационных входов которого подключена к выходу блока регистров, к входу которого подключена35 группа входов размера максимального свободного участка внешней памяти устройства, -й ( = 1, ш) выход блока выбора минимального числа подключен к входу -го формирователя им 40 пульсов группы, выход которого подключен к .-м входам с 1-го по (ш -1)-й элементов ИЛИ-НЕ группы, выход 1-го ( = 2, ш) формирователяимпульсов группы соединен с первымвходом -го (х = 2, ш) элемента Игруппы, выход -го (д = 1, ш - )элемента ИЛИ-НЕ группы подключен квторому входу -го (1 = 2, т) элемента И, выход которого соединен свходом сброса 1-го блока анализа сво.бодньи участков внешней памяти группы, выход первого формирователя импульсов группы подключен к входусброса первого блока анализа свободных участков внешней памяти группы,выход д-го блока анализа свободныхучастков внешней памяти группы подключенк 1-му входу блока элементовИЛИ, выход которого подключен к информационному выходу устройства,причем в каждом блоке анализа свободныхучастков внешней памяти группы первый, второй, третий информационные:входы, вход запуска и вход сброса,подключены соответственно к первомувходу блока элементов сравнения, квходам первого и второго блоков регистров и к входам запуска и сбросаблока выбора минимального числа, выход.блока элементов ИЛИ подключен квыходу блока анализа свободных участков внешней памяти группы, выход первого блока регистров подключен квторому входу блока элементов сравнения и к группе информационных входовблока выбора минимального числа, группа установочных входов и выход которого подключены соответственно к выходу блока элементов сравнения и кпервому входу блока элементов И, второй вход и выход которого подключенысоответственно к выходу второго блока регистров и к входам блока элементов ИЛИ..Гун каз 3707/49 оизводственно-полиграфическое предприятие, г. Ужгоро роектная,Тираж 67 НИИПИ Государст о делам изобр , Москва, ЖПодписненного комитета СССтений и открытийРаушская наб., д.