Способ организации многопроцессорной ЭВМ

15/163 НАЦИОНАЛЬНЫЙ ЦЕНТР ИНТЕЛЛЕКТУАЛЬНОЙ СОБСТВЕННОСТИ СПОСОБ ОРГАНИЗАЦИИ МНОГОПРОЦЕССОРНОЙ ЭВМ(71) Заявитель Ефимов Андрей Игоревич(72) Автор Ефимов Андрей Игоревич(73) Патентообладатель Ефимов Андрей Игоревич(57) Способ организации многопроцессорной ЭВМ, заключающийся в представлении всей программно-доступной архитектуры каждого центрального процессора множеством виртуальных процессоров, хранимых в виде векторов программно-доступных регистров в общем блоке управления памятью, отличающийся тем, что для увеличения активного рабочего множества виртуальных процессоров организуют взаимодействие кэш-памяти виртуальных процессоров общего блока управления памятью, блока мониторов виртуальных процессоров, блока секвенсоров транзакций и блока исполнительных устройств,включающего регистровый файл временных переменных, при котором порождаемый поток команд каждого виртуального процессора представляют хранимым в блоке мониторов списком дескрипторов транзакций, в котором каждый дескриптор содержит поля идентификации породивших транзакцию монитора и виртуального процессора, поля головы и хвоста 5350 1 списка хранимых в регистровом файле секвенсора дескрипторов команд транзакции, содержащих поле кода операции и операндов команды, поле индекса дескриптора транзакции-хозяина и отражающую информационную зависимость команды от других команд пару полей, первое из которых содержит число команд-предшественников, результаты исполнения которых ожидает команда, а второе содержит индекс команды-преемника,ожидающей результат исполнения данной команды, исполнение команд организуют секвенсорами транзакций, посредством каждого из которых обслуживают объединяемое тремя очередями однородное в отношении исполняемых команд подмножество исполнительных устройств, причем в первую очередь, индексы головы и хвоста которой находятся в первом регистре секвенсора, включают ожидающие готовности своих операндов команды, во вторую очередь, индексы головы и хвоста элементов которой в соответствии с приоритетом виртуального процессора-хозяина находятся во втором регистре секвенсора, включают готовые к исполнению команды, а в третью очередь, индексы головы и хвоста которой находятся в третьем регистре секвенсора, помещают исполненные команды, при этом предусмотрена реализация общим блоком управления памятью механизма виртуальной памяти с большим множеством идентификаторов адресного пространства, достаточным для однозначной идентификации всех аппаратных объектов ЭВМ и всех динамических виртуальных объектов, таких как виртуальные процессоры и программные процессы, по адресной паре, состоящей из уникального идентификатора адресного пространства, на которое объект отображается, и смещения отображения объекта с точностью до бита, причем все битовое представление идентификатора адресного пространства входит в ассоциативную часть строк общего блока управления памятью, при этом посредством каждого монитора виртуальных процессоров осуществляют предвыборку и дешифрацию порожденного потока команд с формированием очереди транзакций и выделением для первой из очереди, выдаваемой на исполнение транзакции всех необходимых дескрипторов команд и регистров временных переменных из регистрового файла блока исполнительных устройств, причем по очередной выдаваемой на исполнение транзакции монитором сканируют начинающийся с индекса первой команды список образующих транзакцию команд и в соответствии с кодом операции и содержимым поля числа команд-предшественников, результаты исполнения которых ожидает команда, помещают их в очередь готовых к исполнению или очередь ожидающих готовности своих операндов соответствующего коду операции секвенсора, а асинхронно работающими однотипными исполнительными устройствами выбирают и исполняют готовые к исполнению команды, при этом после исполнения любой, не завершающей транзакцию команды, содержащей ссылку на дескриптор команды-преемника,выдавшим исполненную команду секвенсором корректируют поле числа командпредшественников, результаты исполнения которых ожидает команда, которую при его обнулении переводят в очередь готовых к исполнению за счет перемещения ее дескриптора в очередь готовых к исполнению команд секвенсора, соответствующего ее коду операции, с освобождением дескриптора исполненной команды и регистров файла временных переменных, а после исполнения завершающей транзакцию команды, имеющей пустую ссылку на команду-преемника, запускают породивший транзакцию монитор виртуальных процессоров, оканчивая цикл отработки транзакции.(56) Мультипроцессорные системы и параллельные вычисления. - М. Мир, 1976. - С. 384.97114237 , 1999. Изобретение относится к области вычислительной техники и может быть использовано для создания многопроцессорных ЭВМ типа множественный поток команд - множественный поток данных новой архитектуры. Целью изобретения является разработка 2 5350 1 нового способа организации многопроцессорных ЭВМ, обеспечивающего существенное улучшение соотношения производительность/стоимость на основе увеличения числа параллельно исполняемых последовательных процессов и сохраняющего возможность распараллеливания исполнения потока команд отдельного процесса в соответствии с существующими методами за счет увеличения числа исполнительных устройств с гарантией их полной загрузки. Существует два взаимно дополняющих подхода увеличения скорости вычислений наиболее широко используемых многопроцессорных ЭВМ типа множественный поток команд - множественный поток данных 1, 4-7. Первый связан с увеличением числа процессоров и усложнением архитектуры за счет выделения каждому процессору собственной локальной оперативной памяти при сохранении общей памяти. Этот подход преимущественно используется в дорогостоящих средних и больших ЭВМ. Второй подход, который принято называть поддержкой параллелизма на уровне команд, связан с применением процессоров с суперскалярной и широкой команды архитектурами, которые для увеличения скорости исполнения команд одного потока используют выделение и исполнение допускающих параллельную обработку независимых операций несколькими исполнительными устройствами одновременно 5-8. Этот подход стал широко применяться и в недорогих процессорах персональных ЭВМ 8. Однако увеличение числа исполнительных устройств не всегда приводит к экономически оправданному повышению скорости вычислений из-за информационных зависмостей команд в реальных программах, представляющих в основном последовательные алгоритмы, которые приводят к простоям исполнительных устройств, составляющих основные части сложности и стоимости современных процессоров. Основной недостаток известных подходов повышения параллелизма на уровне команд, связанный с информационными зависимостями команд одного потока, может быть преодолен за счет загрузки исполнительных устройств командами заведомо независмых потоков. В данном изобретении предлагается создавать множество независимых потоков за счет виртуальных процессоров, концепция которых основывается на принципе взаимодействия последовательных процессов, сформулированом Э. Дейкстрой в классической работе 2. В соответствии с ней параллельные вычисления выполняются множеством слабо связанных последовательных процессов, взаимодействующих в дискретные моменты времени через общие переменные и исполняющихся с произвольными относительными скоростями в диапазоне от нуля до бесконечности. При доказательстве правильности механизмов синхронизации последовательных процессов считается, что между окончанием одной машинной команды, например команды чтения общей переменной, и окончанием следующей, выполняющей ветвление по считанному значению в одном процессе,может пройти промежуток времени, в течение которого другой процесс успеет прочитать и изменить значение общей переменной и тем самым сделать некорректным ветвление по устаревшему значению этой переменной в первом процессе. Для предотвращения таких ситуаций в мультипроцессорных ЭВМ реализованы специальные команды синхронизации, выполняющие чтение и изменение значения слова памяти как одну неделимую операцию 1, 2, 3. Исходя из приведенной выше концепции взаимодействия последовательных процессов виртуальный процессор определяется как хранимое представление набора программно-доступных регистров процессора, называемых далее архитектурными регистрами,необходимое и достаточное для возобновления исполнения последовательного процесса с любой возможной команды. Очевидно, что для исполнения любой команды определенного таким образом виртуального процессора традиционная архитектура процессоров является избыточной. В самом деле, для выполнения отдельной команды достаточно более простое, чем традиционный процессор устройство, которое может выбрать архитектурную команду с операндами, кодирование которых однозначно определяет код и данные 3 5350 1 связанного с виртуальным процессором последовательного процесса и передать ее соответствующему коду операции исполнительному устройству, которое исполнит команду, выполнив шаг продвижения последовательного процесса. Работая как мультиплексор потока команд такое устройство в сочетании с множеством исполнительных устройств может продвигать вычисления во множестве виртуальных процессоров. Концепция виртуальных процессоров для сокращения объема оборудования и согласования быстродействующей логики с медленной ферритовой памятью была использована в реализации периферийной ЭВМ систем 4. Мультипроцессорная периферийная ЭВМ строилась в виде единственных устройства управления и исполнительного устройства, которые поочередно подключались к одному блоку регистров из набора блоков, образуя в выделенный временной интервал виртуальный процессор. Совокупность таких виртуальных процессоров ведет себя как обычный симметричный мультипроцессор. Этот способ организации мультипроцессорных ЭВМ является наиболее близким аналогом-прототипом предлагаемого в изобретении способа. Основным недостатком способа-прототипа является избыточность, связанная с тем, что для исполнения любой команды к блоку регистров с загруженным дескриптором последовательного процесса подключается практически вся аппаратура традиционного процессора, тогда как достаточным является подключение единственного соответствующего команде исполнительного устройства. Сущность изобретения составляет способ организации многопроцессорной ЭВМ, заключающийся в представлении всей программно-доступной архитектуры каждого центрального процессора виртуальным процессором, хранимым в виде вектора архитектурных регистров в общем устройстве управления памятью ЭВМ, отличающийся тем, что при исполнении любой команды любого виртуального процессора всей совокупностью аппаратных устройств ЭВМ используется непосредственно хранимое представление архитектурных регистров процессора, тогда как известные способы организации ЭВМ требуют в момент исполнения любой команды загруженности всей совокупности архитектурных регистров на аппаратных регистрах процессора. На фигуре приведена структурная схема многопроцессорной ЭВМ, организованной на основе предлагаемого способа. В отличие от известных ЭВМ в ней отсутствуют центральные процессоры в традиционном понимании, а вместо них вводятся три дополнительных блока блок мониторов виртуальных процессоров 1, блок секвенсоров транзакций 2, кэш виртуальных процессоров 3, дополняющий блок управления памятью 4, традиционно содержащий кэш команд 5 и кэш данных 6, обеспечивающий во взаимодействии с модулями оперативной памяти 7 реализацию общего механизма виртуальной памяти для всех виртуальных процессоров. Кроме того, модифицируется блок исполнительных устройств 8. Каждый входящий в блок 1 монитор виртуальных процессоров 9-1 - 9- в своих регистрах хранит голову и хвост списка своих виртуальных процессоров из множества 25-1 25- загруженных в кэш виртуальных процессоров 3. Незагруженные в кэш 3 виртуальные процессоры хранятся в виртуальной памяти системных процессов и по мере необходимости, связанной с изменением статуса активности связанных с ними процессов, загружаются в кэш 3. Для каждого потока исполняемых команд своих виртуальных процессоров монитор создает отдельные транзакции, состоящие из хранимых в регистровом файле монитора дескрипторов транзакций 10-1 - 10- и хранимого в блоке секвенсоров 2 двунаправленного списка дескрипторов команд транзакций, голова и хвост которого помещается в поля 11 и 12 дескриптора транзакции. Идентификаторы породивших транзакцию монитора и виртуального процессора также помещаются в поля 13 и 14 дескриптора транзакции. Блок секвенсоров 2 содержит одинаковые секвенсоры транзакций 15-1 - 15-, каждый из которых обслуживает однородное в отношении отрабатываемых команд подмножество исполнительных устройств блока 8. Команды представляются хранимыми в регистровом файле команд 16 дескрипторами 17, упорядоченными в виде трех очередей. В первой очереди, индексы головы и хвоста которой находятся в регистре секвенсора 18, содержатся 4 5350 1 ожидающие готовности своих операндов команды. Во второй очереди, индексы головы и хвоста элементов которой в соответствии с приоритетом виртуального процессорахозяина находятся в последовательности регистров секвенсора 19-1 - 19-р, содержатся готовые к исполнению команды. В третьей очереди, индексы головы и хвоста которой находятся в регистре секвенсора 20, буферизуются исполненные команды, ожидающие освобождения использованных в транзакции ресурсов. В терминах своих команд транзакция представлена следующим образом. Дескриптор команды 17 помимо кода операции и операндов в поле 21 содержит индекс дескриптора своей транзакции-хозяина в поле 22 и отражающие ее информационную зависимость от других команд пару полей 23 и 24, первое из которых содержит число команд-предшественников, результаты исполнения которых ожидает данная команда, а второе содержит индекс командыпреемника, ожидающей результат исполнения данной команды. Известный механизм виртуальной памяти на основе адресных пространств, реализуемый блоком управления памятью 3, модифицируется в направлении однозначного отображения непосредственно на аппаратном уровне всех физических и виртуальных объектов ЭВМ на собственные адресные пространства за счет увеличения разрядности поля идентификатора адресного пространства и его полного включения в ассоциативную часть строк всех кэшей. Хранимое в кэше 3 представление каждого извиртуальных процессоров 25-1 - 25 имеет следующую структуру. Ассоциативная часть строк кэша содержит идентификатор адресного пространства, на которое отображается виртуальный процессор и старшую часть смещения блока архитектурных регистров. Информационная часть строки содержит соответствующий смещению блок архитектурных регистров 26, причем блок с нулевым смещением в начале содержит служебную информацию, в которой представлена общая длина служебной части 27, тип виртуального процессора 28, его приоритет 29 для запросов исполнительных устройств и поле 30 для прошивки в списки операционной системы или монитора виртуальных процессоров. Блок исполнительных устройств 8 содержит известные исполнительные устройства 31-1 - 31-е и регистровый файл временных операндов 32. Исполнительные устройства 311 - 31-е модифицированы в направлении организации единообразного доступа к любым операндам команд по адресным парам, включающим идентификатор адресного пространства операнда и его смещение внутри этого пространства с точностью до бита. Операндам-регистрам рабочего файла 32 и операндам-литералам выделяется пара специальных идентификаторов адресного пространства. Первый многоканальный тракт обмена 33 обеспечивает передачу информации между блоками мониторов виртуальных процессоров 1, секвенсоров транзакций 2 и исполнительных устройств 8, а также передачу информации внутри этих блоков, второй тракт 34 обмен с блоком управления памятью 4. По тракту 35 осуществляется обмен блока управления памятью 4 с блоками памяти 7. Работа ЭВМ, организованной на основе предложенного в изобретении способа, в общих чертах выглядит следующим образом. Операционная система по мере необходимости,связанной с изменением статуса активности процессов, загружает в кэш 3 виртуальные процессоры 25-1 - 25-, создавая активное рабочее множество исполняемых процессов, и распределяет их в соответствии с типом по мониторам виртуальных процессоров 9-1 - 9-. Каждый монитор виртуальных процессоров осуществляет предвыборку и дешифрацию потока архитектурных команд, формируя очередь транзакций, выделяет для первой из очереди, выдаваемой на исполнение транзакции 10-1, все необходимые дескрипторы команд 17 и регистры рабочего файла 32 для временных переменных. По очередной подаваемой на исполнение транзакции 10-1 монитор сканирует начинающийся с индекса первой команды 11 список образующих транзакцию команд 17 и в соответствии с кодом операции 21 и полем счетчика ожидаемых команд 22 помещает их в 5 5350 1 очередь готовых или очередь ожидающих своих операндов соответствующего коду операции секвенсора. Асинхронно работающие однотипные исполнительные устройства 31-1 - 31-е каждого секвенсора выбирают готовые к исполнению команды из своей общей групповой очереди,исполняют их, причем после исполнения любой не завершающей транзакцию команды,содержащей ссылку 24 на дескриптор команды-преемника, корректируется счетчик ожидаемых команд 23 последней. При его обнулении команда становится готовой к исполнению и переводится в очередь готовых за счет перемещения ее дескриптора 17 в очередь готовых команд секвенсора, определяемого ее кодом операции в поле 21. Соответственно после исполнения завершающей транзакцию команды, имеющей пустую ссылку 24 на ожидающую результата ее исполнения команду, запускается породивший транзакцию монитор виртуальных процессоров, заканчивая цикл отработки транзакции и запуская на исполнение следующую из очереди предвыборки. Ниже приводится пример представления и исполнения транзакции, реализующей вычисления по формуле / (-) с распараллеливанием на уровне команд. Считается, что используются двухадресные исполнительные устройства, которые могут исполнять арифметические операции только над операндами в регистровом файле и помещать результат на место первого операнда. Двухадресные команды представлены в виде,(операция, оп 1 рез, оп 2,гдеопределяет условный номер дескриптора команды 17 в регистровом файле 16,элементыи , соответствующие полям 23 и 24 в дескрипторе команды 17, обозначающим число команд, результатов которых ожидает команда и условный номер дескриптора команды, которая ожидает исполнения данной команды. Элементы в фигурных скобках обозначают код операции, пару операндов команды и результат команды. Создавая транзакцию монитор запрашивает восемь дескрипторов команд 1-8 и четыре регистра рабочего файла под временные переменные 1-4. Первоначально сформированные очереди команд тразакции имеют следующий вид. Очередь готовых команд секвенсора устройств чтения/записи 10,6(чт, 1, а) 20,6(чт, 2, ) 30,7(чт, 3, с) 40,7(чт, 4, ) Очередь ждущих команд секвенсора устройств чтения/записи 51,0(зп, 1, ) Очередь ждущих команд секвенсора устройств сложения/вычитания 62,8(сл, 1, 2) 72,8(выч, 3, 4) Очередь ждущих команд секвенсора устройств деления/умножения 82,5(дел, 1, 3) После исполнения начальных команд 1 и 2 готовой к исполнению станет команда 6, указанная в поле ожидающей для них. Аналогично после команд 3 и 4 готовой к исполнению станет команда 7. При наличии четырех исполнительных устройств чтения/записи возможно параллельное исполнение всех команд 1-4. В результате исполнения первоначального списка готовых команд освободятся дескрипторы команд 1-4, очередь готовых команд секвенсора чтения/записи станет пустой,а непустые очереди секвенсоров примут следующий вид. Очередь ждущих команд секвенсора устройств чтения/записи 5,0(3, 1, ) Очередь готовых команд секвенсора устройств сложения/вычитания 6 5350 1 62,8(сл, 1, 2) 72,8(выч, 3, 4) Очередь ждущих команд секвенсора устройств деления/умножения 82,5(дел, 1, 3) При наличии двух исполнительных устройств сложения/вычитания возможно параллельное исполнение команд 6 и 7. После исполнения команд 6 и 7 пустой станет очередь готовых команд секвенсора устройств сложения/вычитания и освободятся дескрипторы команд 6 и 7, пустой станет очередь ждущих команд секвенсора устройств деления/умножения и очереди примут следующий вид. Очередь ждущих секвенсора устройств чтения/записи 5,0(3, 1, ) Очередь готовых команд секвенсора устройств деления/умножения 82,5(дел, 1, 3) После исполнения команды 8 и за ней 5 завершенной станет вся транзакция и монитор сможет освободить все регистра рабочего файла, использованные для временных переменныех 1-4. Для ускорения освобождения регистров рабочего файла в структуру команды добавлены битовые поля, которые обозначают возможность освобождения соответствующих регистров сразу после исполнения команды. Предлагаемый механизм транзакций позволяет единообразно реализовать как простейшую технику последовательного исполнения команд в простом мониторе, так и известные приемы распараллеливания в суперскалярном мониторе или мониторе,отрабатывающем широкие команды без каких-либо архитектурных ограничений на число одновременно исполняемых команд одной транзакции. Кроме того, предложенная структура транзакций позволяет параллельно отрабатывать вычисления с многоместными операциями. Поскольку списки команд секвенсоров могут представлять транзакции гарантированно независимых потоков архитектурных команд различных виртуальных процессоров, за счет увеличения активного рабочего множества виртуальных процессоров можно полностью устранить простои исполнительных устройств, которые в настоящее время являются наиболее дорогостоящими и сложными в составе многопроцессорных ЭВМ. С другой стороны, за счет наращивания числа исполнительных устройств того или иного типа можно масштабировать степень параллелизма многопроцессорных ЭВМ как на уровне одновременно исполняемых процессов, так и на уровне команд одного потока до любого желаемого уровня, сохраняя опять же за счет увеличения активного рабочего множества виртуальных процессоров полную загруженность исполнительных устройств. Все блоки, реализующие изложенный в изобретении способ, могут быть построены на основе типовых элементов современной цифровой схемотехники, используемой при построении многопроцессорных систем - сверхоперативной памяти для регистрового файла операндов и регистровых файлов дескрипторов очередей, кэш-контроллеров разного уровня и модулей оперативной памяти для блока управления памятью, высокоскоростных шин для организации связей внутри блоков и матрицы координатной коммутации 3 для организации связей блоков между собой. Разработка блоков монитора виртуальных процессоров и секвенсоров транзакций не может вызвать каких-либо принципиальных трудностей, так как в них реализованы обычные функции существующих устройств выборки команд. Модификация исполнительных устройств затрагивает только устройства чтения/записи в части организации обмена с устройством управления памятью по виртуальным адресам с расширенным полем идентификатора адресного пространства также не может вызвать принципиальных проблем. На основе изложенного можно сделать заключение об осуществимости предложенного в изобретении способа. 7 5350 1 Таким образом, цель изобретения, заключающаяся в разработке нового способа организации многопроцессорных ЭВМ, обеспечивающего существенное улучшение соотношения производительность/стоимость на основе увеличения числа параллельно исполняемых последовательных процессов и сохраняющего возможность распараллеливания исполнения потока команд отдельного процесса в соответствии с существующими методами за счет увеличения числа исполнительных устройств с гарантией их полной загрузки, представляется достигнутой. Источники информации 1. Бабаян Б.А., Сахин Ю.Х. Система Эльбрус // Программирование. - 1980.-6. 2. Дейкстра Э. Взаимодействие последовательных процессов // Языки программирования. - М. Мир, 1972. - С. 9-86. 3. Дейтел Г. Введение в операционные системы В 2-х т. Т. 1. Пер. с англ. - М. Мир,1987. - С. 359. 4. Мультипроцессорные системы и параллельные вычисления / Под ред. Ф.Г. Энслоу. Национальный центр интеллектуальной собственности. 220034, г. Минск, ул. Козлова, 20. 8