СПОСОБ ОРГАНИЗАЦИИ МНОГОПРОЦЕССОРНОЙ ЭВМ Российский патент 2007 года по МПК G06F15/16 G06F15/173 

Изобретение относится к области вычислительной техники и может быть использовано для создания многопроцессорных многопоточных ЭВМ новой архитектуры. Целью изобретения является разработка нового способа организации ЭВМ, свободного от основного недостатка существующих многопоточных процессоров - накладных расходов из-за перезагрузки дескрипторов нитей при изменении множества исполняемых нитей, и улучшение на этой основе соотношения производительность/стоимость ЭВМ.

Многопоточная архитектура первоначально была использована в середине шестидесятых годов для сокращения объема оборудования за счет согласования быстродействующей логики с медленной ферритовой памятью в периферийных ЭВМ суперкомпьютера CDC6600 [4]. Периферийная ЭВМ строилась в виде единственных устройства управления и исполнительного устройства, которые поочередно подключались к одному блоку регистров из набора блоков, образуя в выделенный временной интервал виртуальный процессор. Совокупность таких виртуальных процессоров ведет себя как многопоточная ЭВМ в современной терминологии [5], исполняющая множество нитей, представленных загруженными во все блоки регистров дескрипторами.

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

Эта проблема решена в многопоточных процессорах [5], в которых устройство выборки в каждый машинный такт может осуществлять выборку команд разных независимых потоков и передавать их на вход исполнительного конвейера. Например, в разработанном еще в 1990 году суперкомпьютере Тега [5] используется исполнительный конвейер с шириной 3 и глубиной 70, а исполнительное устройство работает со 128 нитями, причем около 70 нитей обеспечивают полную загрузку исполнительного конвейера.

Внутри операционной системы нить в состояниях исполнения или ожидания представлена своим дескриптором, однозначно идентифицирующим нить и контекст ее исполнения - контекст процесса. Процесс является системным объектом, которому выделяется отдельное адресное пространство, называемое также контекстом процесса. Корень представления контекста активных процессов размещается в аппаратных регистрах устройства управления виртуальной памятью исполняющего процессора. Представление нити, позволяющее приостанавливать и возобновлять работу нити в контексте процесса-хозяина, принято называть виртуальным процессором [2, 3, 5]. Работа операционной системы по управлению мультипрограммной смесью в общем виде [2] сводится к созданию и уничтожению процессов и нитей, загрузке активируемых виртуальных процессоров на аппаратные регистры и переписи в память виртуальных процессоров, переходящих по каким-либо причинам в состояние ожидания. В контексте процесса исполняются независимые последовательные активности-нити, причем механизм виртуальной памяти обеспечивает защиту от неконтролируемого влияния нитей разных процессов друг на друга. В соответствии с классической работой Дейкстры [1], описывающей сущность взаимодействия последовательных процессов, нити являются базовыми элементами, на основе синхронизированного исполнения которых строятся любые параллельные вычисления. Множество последовательных независимых активностей в любой ЭВМ формируется по следующим причинам:

- явное создание нити операционной системой;

- запуск обработки асинхронно выдаваемого программного сигнала;

- запуск обработки асинхронно возникающего аппаратного прерывания.

Эти активности, отображаемые в операционных системах нитями в каком-либо виде, могут находиться в состояниях исполнения либо ожидания события-причины активации. Поскольку допустимое множество загруженных на регистры дескрипторов нитей во всех известных многопоточных машинах значительно меньше всего возможного множества нитей, для возобновления исполнения какой-либо приостановленной нити требуется сброс всего сосредоточенного представления дескриптора другой нити из аппаратных регистров процессора в память и загрузка дескриптора активируемой нити в обратном направлении. Например, в многопоточной ЭВМ Тега [5] дескриптор нити состоит из 41 слова длиной 64 бита и время простой перезагрузки сравнимо со временем обработки прерывания. Если же происходит сложное переключение на нить из другого домена защиты (исполняющуюся в контексте другого процесса), происходит дополнительная перезагрузка представляющих домен таблиц виртуальной памяти. Очевидно, что такие перезагрузки являются основными накладными расходами, препятствующими применению мощных многопоточных процессоров в системах управления большими базами данных, в больших встроенных системах и ряде других важных сфер, в которых исполняющиеся программы создают очень большое множество часто переключающихся процессов и нитей.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Литература

1. Дейкстра Э. Взаимодействие последовательных процессов // Языки программирования. М.: Мир, 1972, с.9-86.

2. Дейтел Г. Введение в операционные системы: В 2-х т. Т.1. Пер. с англ. М.: Мир, 1987 - 359 с.

3. Ефимов А.И. Способ организации многопроцессорной ЭВМ. Описание изобретения к патенту Республики Беларусь N 5350.

4. Мультипроцессорные системы и параллельные вычисления / Под ред. Ф.Г.Энслоу. М.: Мир, 1976 - 384 с.

5. Robert Alverson, David Callahan, Daniel Cummings, Brian Koblenz, Allan Porterfield, Burton Smith (1990). The Tera Computer System. In Proc. Int. Conf. Supercomputing, Amsterdam, The Netheriand, 1990, June, pp.1-6.

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

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