Вычислительная система
(57) ТЕКСТ РЕФЕРАТА ОТСУТСТВУЕТ
Настоящее изобретение относится к области вычислительной техники и может быть использовано при организации связи и управления в многопроцессорных вычислительных системах, обеспечивающих эффективное использование оборудования и сколь угодно высокий уровень распараллеливания вычислительных процессов на широком круге задач. Как известно, в настоящее время для распараллеливания вычислений используются два основных принципа организации связей в многопроцессорных системах: принцип общей шины и принцип однородной структуры. При подключении центральных процессоров и блоков оперативной памяти к общей шине возникают трудности, мешающие эффективному распараллеливанию вычислительного процесса на большое число устройств. С одной стороны необходимость разделения шины для обслуживания большого числа устройств (особенно высокоскоростных) требует высокой скорости и передачи сигналов по этой шине. С другой стороны подключение к шине большого числа устройств (особенно размещенных в разных шкафах) приводит к увеличению ее длины, а, следовательно, и к уменьшению скорости передачи информации. К этому нужно добавить конструктивные трудности, связанные с организацией высокоскоростного обмена между шкафами и трудности комплексной наладки системы. Поскольку существующие методы управления в многопроцессорных системах с общей шиной требуют высокой скорости информационного обмена, мы сталкиваемся здесь с противоречием, препятствующим значительному увеличению числа подключаемых к общей шине устройств. Другая трудность в системах с общей шиной прогрессирующая с ростом уровня распараллеливания сложность управления вычислительным процессом, вызываемая необходимость разделения шины между устройствами и проблемами конкуренции процессоров при обращениях к одним и тем же блокам ОЗУ. Указанные трудности приводят к тому, что на принципе общей шины строятся системы лишь с небольшим числом процессоров (чаще всего 2-8). В качестве примеров можно указать американскую систему STAR 100, советскую систему ЭЛЬБРУС-2 и др. Второй тип организации связей это однородные структуры, когда однотипные (чаще всего упрощенные) процессоры располагаются в виде плоской или пространственной решетки, с которой связываются между собой соседние элементы. Построенные по этой схеме вычислительные системы позволяют осуществлять глубокое распараллеливание векторно-матричных операций, как это делается, например, в американской вычислительной системе 1L L IAC IV. Если же структура связей между отдельными частями распараллеливаемой задачи не соответствует структуре решетки, то эффективность распараллеливания в подобных системах резко падает, а управление вычислительным процессом резко усложняется. Причиной этого является необходимость использования большей части процессоров не по основному их назначению, а для простого транзита информации при организации дальних связей. То же самое будет, очевидно, и при любой другой фиксированной системе связей. Организованные по этому принципу вычислительные системы будут непременно узко специализированными в том смысле, что высокая производительность и эффективное использование оборудования достигается ими лишь на некотором классе задач. Второй недостаток подобной структуры связей (даже применительно к соответствующим ей задачам) ее несогласованность с конструктивной иерархией, принятой в вычислительной технике: пока процессоры размещаются в пределах одного конструктивного элемента (скажем, шкафа), то связи между процессорами будут достаточно короткими и, следовательно, быстрыми. При расширении системы это преимущество теряется. Наличие же системы связей с разными электрическими характеристиками, различающихся к тому же конструктивным выполнением, приводит к усложнению отладки и эксплуатации системы и к уменьшению ее производительности за счет снижения скоростей информационного обмена. К описанному типу связей примыкает организация связей специализированных процессорных элементов в быстродействующих однопроцессорных ЭВМ, работающих по принципу трубопровода (pipe-line) называемому также принципом синхронной накачки. Процессорные элементы специализируются на выполнении отдельных микроопераций, на которые разбиваются машинные команды. Поскольку распараллеливание здесь осуществляется не на уровне задач, а на уровне машинных команд, оно более универсально, чем в предыдущем случае. Однако, такой подход к распараллеливанию ограничивает его количественно. Число процессорных элементов, которые можно одновременно эффективно задействовать в подобных системах, обычно не превышает одного десятка. Описанный принцип широко используется в современной вычислительной технике. Наиболее близкой по технической сущности является вычислительная система, построенная по иерархическому принципу. Она содержит группы вычислительных машин и модули коммутации, причем вычислительные машины каждой группы соединены через шины связи с соответствующим модулем коммутации. На каждом уровне модули коммутации объединены в группы и модули коммутации каждой группы более низкого уровня соединены через шины связи с соответствующим модулем коммутации более высокого уровня. Недостатками этой системы являются: низкая гибкость системы и степень распараллеливания вычислительного процесса; с ростом уровня иерархии резко повышаются требования к скоростям информационных обменов; низкий коэффициент использования оборудования, обусловленный тем, что каждая вычислительная машина или их группа может работать только в составе всей системы, а также централизацией поступления заданий в систему. Кроме того, используемые до сих пор способы организации связей и управления в многопроцессорных вычислительных системах имеют два недостатка. Первый недостаток несогласованность этих способов с иерархией конструктивных элементов, из которых строятся вычислительные машины и системы. Второй недостаток это невозможность устpанить противоречие между универсальностью и глубиной распараллеливания: эффективное распараллеливание на большое число процессоров (или процессорных элементов) достигается лишь на узких классах задач, на которые специализирована соответствующая вычислительная система. Эти недостатки не устраняются и при комбинациях описанных выше способов организации связей в системе. Создающееся положение вызвало появление ряда работ, в которых предлагается гибкая структура вычислительных систем, настраивающаяся на задачи различных классов. Однако, эти работы носят чисто теоретический характер и не предлагают конкретных технических решений, позволяющих устранить упомянутые выше недостатки. Целью настоящего изобретения является повышение гибкости системы, снижения требований к скоростям информационных обменов, повышения коэффициента использования оборудования. Поставленная цель достигается тем, что в вычислительную систему, содержащую вычислительные машины, коммуникационно-управляющие процессоры, распределенные по уровням иерархии, и внешние устройства, введены анализаторы процессов вычислений по числу вычислительных машин и коммуникационно-управляющих процессоров, причем каждая вычислительная машина соединена информационной и управляющей шинами с соответствующим анализатором процессов вычислений, соединенным информационной и управляющей шинами с соответствующим коммуникационно-управляющим процессором первого уровня, а каждый коммуникационно-управляющий процессор каждого уровня иерархии через соответствующий анализатор процессов вычислений соединен с соответствующим коммуникационно-управляющим процессором соседнего более высокого уровня, причем каждый коммуникационный процессор соединен шиной связи с соответствующим внешним устройством, а также тем, что каждый анализатор процессов вычислений содержит четыре группы регистров, регистр сдвига, три коммутатора, пять схем сравнения, счетчик, два сумматора-вычитателя, сумматор, шесть регистров, группу триггеров, две группы коммутаторов, дешифратор, два элемента ИЛИ, элемент И, причем входы регистров первой и второй групп и всех шести регистров соединены с информационной шиной анализатора, соединяющей анализатор с коммуникационно-управляющим процессором более высокого уровня иерархии, выходы регистров первой, второй и третьей групп соединены с информационной шиной, соединяющей анализатор с коммуникационно-управляющим процессором более низкого уровня иерархии или с вычислительной машиной, группа входов первого сумматора-вычитателя, первые входы первого коммутатора, триггеров группы, входы регистров третьей группы соединены с управляющей шиной, соединяющей анализатор с коммуникационно-управляющим процессором более низкого уровня иерархии или с вычислительной машиной, выходы триггеров группы соединены с входами соответствующих регистров четвертой группы и соответствующих коммутаторов первой и второй групп, выходы коммутаторов первой и второй групп соединены с соответствую- щими входами соответствующих регистров третьей группы, выход одного из регистров первой группы соединен с управляющими входами коммутаторов первой группы, выход одного из регистров второй группы соединен с управляющими входами коммутаторов второй группы, выходы регистров четвертой группы соединены с группой входов первого коммутатора, выходы регистра сдвига соединены с вторыми входами триггеров группы, выходы которых через последовательно соединенные второй коммутатор и первый элемент ИЛИ соединены с управляющим входом первого сумматора-вычитателя, выходы которого и первого регистра соединены с входами первой схемы сравнения, первый выход которой соединен с первыми входами элемента И и третьего коммутатора, второй и третий входы которого соединены с вторым выходом первой схемы сравнения, первый выход первого коммутатора через второй сумматор-вычитатель соединен с первыми входами второй и третьей схем сравнения, вторые входы которых соединены с выходами соответственно второго и третьего регистров, первый выход второй схемы сравнения соединен с вторым входом элемента И и четвертым входом третьего коммутатора, пятый и шестой входы которого соединены с вторым выходом второй схемы сравнения, выход третьей схемы сравнения соединен с первым входом второго элемента ИЛИ и с вторым входом первого коммутатора, второй выход которого через сумматор соединен с первым входом четвертой схемы сравнения, второй вход которой и первый вход дешифратора соединены с выходом четвертого регистра, выход дешифратора соединен с первым входом счетчика, третьим входом первого коммутатора, управляющим входом второго коммутатора и вторым входом второго элемента ИЛИ, выход которого соединен с входом регистра сдвига, выходы пятого и шестого регистров соединены с входами пятой схемы сравнения, выходы четвертой схемы сравнения соединены с вторыми входами счетчика и дешифратора, выходы счетчика, первого элемента ИЛИ, элемента И, третьего коммутатора и пятой схемы сравнения соединены с управляющей шиной, соединяющей анализатор с коммуникационно-управляющим процессором более высокого уровня иерархии. Предлагаемая вычислительная система выполнена по иерархически модульному принципу, при этом модуль любого уровня иерархии представляет собой законченный в конструктивном и функциональном отношении блок с универсальным внешним интерфейсом, который помимо использования в системе, может использоваться автономно в качестве отдельной ЭВМ или вычислительной системы. В уровни иерархии эти модули соединены посредством коммуникационно-управляющих процессоров и анализаторов процессов вычислителей, реализующих метод макроконвейеризации вычислений (распараллеливание циклов или систем вложенных друг в друга циклов). Некоторое число модулей объединены в конструктивные элементы, иерархия которых согласована с иерархией коммуникационно-управляющих процессоров, анализаторов процессов вычисления и соответствующих им модулей. Блок-схема, иллюстрирующая принцип построения предлагаемой вычислительной системы приведена на фиг. 1; блок-схема анализатора процессов вычислений приведена на фиг. 2. Вычислительная система содержит вычислительные машины 1 (рабочие процессоры), коммуникационно-управляющие процессоры 2, которые шинами связи соединены с внешними устройствами 3, а через анализаторы процессов вычисления 4 соединены с коммуникационно-управляющими процессами верхнего (нижнего уровня) иерархии или вычислительными машинами (рабочими процессорами). Вычислительная машина 1 (рабочий процессор) представляет микро-ЭВМ, состоящая из арифметико-логического устройства, устройства управления, небольшого ОЗУ и последовательного или малоразрядного канала для передачи данных и управляющих сигналов. Она предназначена для выполнения рабочих программ и их отдельных блоков. Она представляет собой элементарный модуль, который конструктивно оформляется в виде ТЭЗа первого уровня, размер которого определяется достигнутым уровнем электронной технологии. Некоторое фиксированное число элементарных модулей (рабочих процессоров) объединяются в модуль первого уровня. Объединяющими их элементами являются коммуникационно-управляющий процессор 2 и анализаторы процессов вычисления 4. Коммуникационно-управляющий процессор 2 состоит из управляющего процессора с небольшим ОЗУ и коммутатора (коммутационного поля) способного коммутировать между собой каналы рабочих процессоров, управляющего процессора и несколько малоразрядных шин внешних выводов. Внешние выводы предназначены для выбора и организации связи на следующем уровне иерархии. Они могут снабжаться в случае необходимости усилителями и формирователями сигналов. Управляющий процессор предназначен для интерпретации второго уровня программного продукта и управления обменными операциями между подчиненными ему модулями. Модули первого уровня объединяются в модули второго уровня посредством коммуникационно-управляющего процессора и анализаторов процессов вычислений. При этом выходы коммуникационно-управляющих процессоров 2 через анализаторы процессов вычислений 4 соединяются с входами коммуникационно-управляющих процессоров третьего уровня. Аналогично образуются и модули более высоких уровней. На каждом уровне при этом имеются свои коммуникационно-управляющие процессоры и анализаторы процессов вычислений, а каждый модуль имеет законченное конструктивное оформление. Если в соответствующий конструктивный элемент (например, шкаф) могут быть вмонтированы те или иные внешние устройства 3 (дисководы, дисплеи, перфораторы и др.), то через соответствующие шины связи они подключаются к коммутационному полю этого конструктивного элемента. Достигая на некотором уровне размера отдельного шкафа, конструктивные модули на следующем уровне иерархии выступают в качестве классических вычислительных систем (системы шкафов, отдельных дисководов, АЦПУ и других устройств). Следующий уровень иерархии объединение нескольких вычислительных систем в рамках одного ВЦ, а более высокие иерархии продолжаются уже в рамках сетей ВЦ с соответствующими изменениями в связных интерфейсах. Описанная структура организации системы позволяет организовать и оперативно перестраивать в процессе работы любые связи между рабочими процессорами и другими составляющими ее элементами. Однако, в отличие от описанных выше систем, эти связи будут гораздо более медленными и при обычных методах планирования и управления параллельными вычислительными процессами сделают предлагаемую систему не эффективной. Поэтому в заявке предлагается новый принцип планирования и управления вычислительным процессом, позволяющим осуществлять глубокое эффективное распараллеливание широкого круга задач при относительно малых скоростях информационного обмена. Для понимания этого принципа необходимо прежде всего обратить внимание на то обстоятельство, что при существующей и ожидаемой в ближайшем технологии программирования максимальная длина отдельных программ не превысит нескольких миллионов команд. Если в программе отсутствуют циклы, то для современной однопроцессорной высокопроизводительной ЭВМ потребуется не более секунды, чтобы выполнить такую программу. Для большинства применений (за исключением некоторых задач управления в реальном масштабе времени) такая скорость является вполне достаточной. Поэтому для подавляющего большинства задач, решаемых на ЭВМ, нет необходимости распараллеливать линейные участки программы (последовательные и альтернативные структуры). Следовательно объектом распараллеливания должны стать программные циклы и, особенно, системы вложенных друг в друга циклов (nested loops). Используя современные методы программирования, можно считать рассматриваемые программы структурированными, т.е. не содержащими операторов "go to". Для распараллеливания циклов в таких программах в настоящее время имеется целый ряд методов. Эти методы, будучи применимыми к весьма широкому кругу задач, дают теоретическую схему распараллеливания, включающую в себя распределение вычислительных операций между процессорами, а также описание связей и обменов между ними. Такая схема, однако, оказывается непригодной для практического использования по двум основным причинам. Во-первых, она распараллеливает работу на максимально возможное число процессоров. Таким числом процессоров (тем более свободных) реальная вычислительная система, как правило, не обладает. Во-вторых, при использовании теоретической схемы распараллеливания для каждого процессора количество выполняемых им обменных операций в расчете на одну вычислительную операцию оказывается, как правило, слишком большим. Поэтому эффективная работа такой схемы требует, чтобы скорость обменных операций имела тот же порядок (если не выше), что и скорость вычислительных операций. Поскольку в каждом конкретном случае для распараллеливания требуется своя система связи между процессорами, то удовлетворить последнему требованию практически невозможно: ведь требования гибкости и быстродействия системы связей взаимно противоречивы. Суть предложения, позволяющего получить практическую схему распараллеливания вычислительного процесса, заключается в следующем. В каждом неэлементарном модуле системы ведется учет свободных ресурсов этого модуля: числа свободных рабочих процессоров, суммарного объема их памяти, а также коммутационных ресурсов. Предлагается, что рабочие процессоры объединяются или освобождаются от совместной работы в системе в процессе решения той или иной задачи целиком, не деля свои ресурсы между разными задачами. Пользуясь специальным описанием цикла (включаемым в программную документацию), коммутационно-управляющий процессор совместно с анализаторами процессов вычислений оценивают целесообразность (в соответствии с имеющимися ресурсами) распараллеливания на своем уровне. При отрицательном решении (если ресурсов модуля оказывается недостаточно) осуществляется формирование задания и передача управления коммуникационно-управляющему процессору следующего по иерархии (объемлющего) модуля и т. д. При выходе на коммуникационно-управляющий процессор модуля, содержащего устройства внешней памяти (или дополнительные "внепроцессорные" блоки ОЗУ) оценка производится с учетом этих дополнительных ресурсов. При положительном решении соответствующий коммуникационно-управляющий процессор и подчиненные ему анализаторы процессов вычислений производят распределение работы и настройку связей между входящими в него модулями низшего уровня. Коммуникационно-управляющие процессоры этих модулей совместно с анализаторами процессов вычисления повторяют эту работу для следующих уровней и т.д. пока распределение заданий (программных блоков и данных) и соответствующая настройка связей не будет доведена до уровня элементарных модулей (рабочих процессоров). После этого начинается согласованная работа всех выделенных ресурсов для выполнения заданного цикла или системы вложенных друг в друга циклов, пока не будет достигнут следующий линейный участок программы или ее конец. Распределение работы между модулями производится в соответствии с теоретической схемой распараллеливания таким образом, чтобы замкнуть максимальное число связей внутри каждого модуля, минимизируя тем самым межмодульные обмены. При этом каждый модуль выполняет работу некоторого подмножества процессоров теоретической схемы. Используя понятие окрестности в структурах данных можно показать, что для большого числа важных в практическом отношении задач (задачи математической физики, математической экономики, оптимизации проектирования и управления и др.) распределение заданий между модулями можно выполнить так, что число внешних связей модуля будет относиться к числу его внутренних связей, как площадь замкнутой поверхности в некотором простpанстве к ограничиваемому ею объему. При достаточно большом числе процессоров теоретической схемы, реализуемых в модуле, это отношение может быть сделано сколь угодно малым, причем тем более малым, чем выше уровень соответствующего модуля. Порядок требуемой скорости информационного обмена, приходящегося на модуль, можно оценить произведением величины этого отношения на быстродействие рабочих процессоров. При малой величине этого отношения требования к скорости передачи данных в системе будут поэтому малыми, особенно для модулей высших уровней. Это обстоятельство полностью согласуется с конструктивными возможностями реализации связи между модулями (чем выше уровень соединяемых модулей тем длиннее связи). Особо следует подчеркнуть то обстоятельство, что при распределении задания не только модули высших порядков, но и элементарные модули (рабочие микро-ЭВМ) должны выполнять работу достаточно большого числа процессоров теоретической схемы. Иначе уже на уровне элементарных модулей обменные операции могут занять недопустимо высокий процент времени работы системы и тем самым значительно снизить эффект распараллеливания вычислительного процесса. Практически количество теоретических процессоров, работу которых берет на себя каждая рабочая микро-ЭВМ, определяется, исходя из максимальной возможной загрузки ее ОЗУ. Как указывалось выше, в данной системе предлагается новый принцип планирования и управления вычислительным процессом, осуществляемый коммутационно-управляющим процессором 2 и анализаторами процессов вычислений 4. Анализатор процессов вычислений (фиг. 2) содержит: регистр 5 адреса начала линейного участка, регистр 6 длины линейного участка, регистр 7 номера линейного участка, регистр 8 адреса данных, регистр 9 длины данных, регистр 10 имени данных, регистр 11 адреса начала цикла, регистр 12 адреса конца цикла, регистр 13 номера участка программы и соответствующие им регистр 14 адреса данных, регистр 15 длины данных, регистр 16 имени данных. Указанные регистры входами соединены с информационными шинами анализатора, соединяющие его с блоком памяти коммуникационно-управляющего процессора через его коммутатор. Выходы регистров соединены с информационными шинами анализатора, соединяющие его с входами коммуникационно-управляющего процессора или рабочего процессора (вычислительной машины), который соответствует этому анализатору процессов вычислений. Схема также содержит группу регистров 17 распределения задания, число которых равно числу рабочих процессоров в модуле. Каждый из таких регистров выходами соединен с информационными шинами анализатора, соединяющие его с входами соответствующего рабочего процессора. Входы регистров 17 через группы коммутаторов 18 и 19 соединены с выходами регистров 7 и 13 номеров участков программы. Вход регистров 17 соединен с управляющими шинами анализатора, соединяющие его с коммуникационно-управляющим процессором более низкого уровня ИЛИ с рабочим процессором (вычислительной машины). Другие входы групп коммутаторов 18 и 19 соединены с выходами триггеров 20 занятости рабочих процессоров. Выходы этих триггеров соединены также с входами регистров 21 памяти процессора и через коммутатор 22, логический элемент ИЛИ 23 с входами сумматора-вычитателя 24 числа свободных процессоров в модуле и через управляющую шину анализатора с блоком управления коммуникационно-управляющего процессора. Регистр 25 требуемого числа процессоров через схему сравнения 26 соединен с выходами сумматора-вычитателя 24. Регистр сдвига 27, предназначенный для поиска свободного процессора, выходы соединен с одними из входов триггеров 20. Регистр 28 требуемого объема памяти выходами через схему сравнения 29 соединен с выходами сумматора-вычитателя 30 объема памяти модуля. Выходы схем сравнения 26 и 29 через коммутатор 31 соединены с управляющей шиной, соединяющей анализатор с блоком управления коммуникационно-управляющего процессора. Выходы регистра 32 требуемой памяти участка подключены на входы схемы сравнения 33, на вторые входы которых подключены выходы сумматора-вычитателя 30. Выходы регистра 34 требуемой памяти цикла подключены к входам дешифратора 35, выход которого соединен со счетным входом счетчика 36 требуемого количества процессоров, с одним из входом логического элемента ИЛИ 37, управляющим входом коммутатора 22 и одним из управляющих входов коммутатора 38, входы которого соединены с выходами регистров 21. Выходы регистра 34 также соединены с входами схемы сравнения 39, на вторые входы которой подключены выходы сумматора 40, соединенного входами с одним из выходов коммутатора 38. Выходы схемы сравнения 39 соединены с управляющим входом счетчика 36 и дешифратора 35. Выходы логического элемента ИЛИ 27 соединены с входом сдвигового регистра 27. Схема также содержит регистр 41 приоритета решаемого задания и регистра 42 приоритета поступившего задания, выходами подключенные к входам схемы сравнения 43. Выход счетчика 36, первые выходы схем сравнения 26 и 29 через логический элемент И 44, выходы схемы сравнения 43, соединены с упpавляющими шинами, соединяющие анализатор с коммуникационно-управляющим процессором более высокого уровня иерархии. Входы регистров 25, 28, 32, 34, 41, 42 соединены с информационными шинами анализатора, соединяющие его с коммуникационно-управляющим процессором более высокого уровня иерархии. Каждый рабочий процессор (вычислительная машина) управляющими шинами соединен в своем анализаторе процессов вычислений с вторым управляющим входом коммутатора 38, вторыми входами триггеров 20 и группой входов сумматора-вычитателя 24. Следует отметить, что связи между рабочими процессорами одного модуля равнозначны по требованиям к скоростям информационных обменов. Эти связи осуществляются через коммутатор (коммутационное поле) коммуникационно-управляющего процессора. Рассмотрим работу системы на примере загрузки ее через коммуникационно-управляющие процессоры первого уровня от внешних устройств 3. В исходном состоянии во всех анализаторах процессов вычислений первого уровня записано в сумматорах-вычитателях 24 и 30 соответственно числа рабочих процессоров в модуле и их общая память. При поступлении задания (программы и данных) коммуникационно-управляющий процессор 2 определяет требуемый объем памяти и число рабочих процессоров, достаточных для выполнения задания. Эти данные записываются соответственно в регистры 28 и 25. В регистр 41 заносится приоритет поступившего задания. Только при условии достаточности числа процессоров и их памяти, которое вырабатывается схемами сравнения 26, 29 и логическим элементом И 44, коммуникационно-управляющий процессор получает сигнал на просмотр поступающего задания. Во всех остальных случаях (недостаточное количество процессоров или памяти) схемы сравнения 26, 29 и коммутатор 31 вырабатывают сигнал передачи по соответствующим шинам поступающего задания и его приоритета через коммуникационно-управляющий процессор первого уровня и анализатор процессов вычислений второго уровня в коммуникационно-управляющий процессор второго уровня. Этот процессор, аналогично описанному выше, отыскивает модуль, у которого число процессоров и их память достаточны для выполнения этого задания. Допустим схемы сравнения 26, 29 и логический элемент И 44 вырабатывает сигнал на просмотр коммуникационно-управляющим процессором первого уровня поступающего задания, т. е. число рабочих процессоров и их памяти в модуле достаточно для выполнения задания. При просмотре задания коммуникационно-управляющий процессор осуществляет выделение линейных участков и циклов в программе с их маркировкой (нумерацией), а также определение степени связности между участками программы. Данные, над которыми программа должна осуществлять операции, также маркируются соответствующим образом. Линейные участки и циклы с их номерами, а также степени связности между участками программы записываются в блок памяти коммуникационно-управляющего процессора. После такого разбиения коммуникационно-управляющий процессор записывает в регистр 32 объем требуемой памяти для вычисления линейного участка программы. По сигналу превышения общего объема памяти модуля над объемом памяти записанной в регистр 32, схема сравнения 33 вырабатывает сигнал поиска свободного процессора, который поступает на коммутатор 38 и через логический элемент ИЛИ 37 на сдвиговый регистр 27. Сдвиговый регистр последовательным опросом триггеров 20 занятости процессоров отыскивает свободный процессор путем опроса состояния триггера. Сигнал с выхода триггера 20 занятости процессора поступает на входы регистра 21 памяти процессора и групп коммутаторов 18 и 19. Одновременно этот же сигнал через коммутатор 22, элемент ИЛИ 23, поступает на вход сумматора-вычитателя 24 свободных процессоров, содержимое которого уменьшается на единицу. По этому сигналу коммуникационно-управляющий процессор последовательно записывает в регистр 7 номера участков в программы и через коммутаторы 18 в соответствующий регистр 17 распределения задания. В этот регистр будут записаны все номера линейных участков программы (как указывалось выше они могут быть выполнены достаточно быстро одним процессором). Этим же сигналом содержимое регистра 21 памяти через коммутатор 38 поступает на вход сумматора-вычитателя 30 объема памяти модуля и вычитается из его содержимого, т.е. объем памяти модуля уменьшается на величину объема памяти одного процессора. Перед распределением рабочих процессоров для выполнения того или иного цикла анализатор процессов вычислений осуществляет анализ этого цикла с точки зрения необходимого количества рабочих процессоров и объема памяти. Для этого коммуникационно-управляющий процессор записывает в регистр 34 необходимый объем памяти для всего цикла. Код объема памяти с регистра 34 поступает на схему сравнения 39. По сигналу несравнения (в сумматоре отсутствует какая-либо запись) дешифратор 34 выдает сигнал, который записывает "1" в счетчик 36 требуемого количества процессоров, переключает выходы коммутатора 38 на входы сумматора 40, переключает коммутатор 22 и через сдвиговый регистр 27 триггер 20 занятости процессора считывает содержимое регистра 21 памяти этого свободного процессора, которое через коммутатор 38 поступает на вход сумматора 40. При очередном несравнении требуемой и записанной в сумматор объема памяти производится поиск дополнительного свободного процессора, перепись его памяти в сумматор 40, запись очередной единицы в счетчик 36. Этот процесс повторяется до тех пор, пока не будет определено требуемое количество рабочих процессоров для выполнения цикла по требуемому объему памяти. По сигналу сравнения или превышения схема сравнения 39 передает содержимое счетчика 36 в коммуникационно-управляющий процессор, который по этому сигналу осуществляет разбиение цикла на число участков, равное числу требуемых процессоров. После этого коммуникационно-управляющий процессор записывает в регистр 32 требуемый объем памяти для участка цикла, номер которого будет записан в соответствующий свободный регистр 17 распределения задания по способу записи номеров линейных участков программы. Таким же образом будут распределены все номера участков цикла между рабочими процессорами модуля. После окончания распределения участков программы коммуникационно-управляющий процессор осуществляет запуск рабочих процессоров, на перепись в свою память номеров участков программы из своего регистра распределения задания 17, а затем по сигналу окончания этой операции на считывание из регистров 5, 11, 6, 12, 7, 13 данные о программе (адрес линейного участка, его длину, номер, участка программы), а из регистров 8, 14, 9, 15, 10, 18 считывание информации об адресах данных, их длине и имени. Процесс считывания информации о программе и данных осуществляется последовательно по участкам и идентифицируется по номерам этих участков, ранее записанных в память рабочего процессора. По завершению записи информация о программах и данных в рабочие процессоры коммуникационно-управляющий процессор считывает содержимое сумматоров-вычитателей 24, 30 и регистра 41, т.е. число оставшихся свободных процессоров в этом модуле, их объем памяти и приоритет распределяемого задания и переписывает через коммуникационно-управляющий процессор следующего уровня в подчиненные ему анализаторы процессов вычислений этого уровня. Затем начинается согласованная работа рабочих процессоров над выполнением задания. При окончании выполнения задания каким-либо рабочим процессором, он вырабатывает сигнал, который поступает на коммутатор 38, переводит триггер 20 занятости процессора в исходное состояние, записывает единицу в сумматор-вычитатель 24 числа свободных процессоров и переписывает объем своей памяти из регистра 21 через коммутатор 38 в сумматор-вычитатель 30 объема памяти модуля, где он суммируется с его содержимым. При поступлении нового задания в этот же коммуникационно-управляющий процессор и при наличии достаточного числа свободных процессоров и общей их памяти, анализ и планирование вычислительного процесса происходит вышеописанным способом. В случае же недостаточности рабочих процессоров возникает задача размещения задания с минимизацией связей между процессорами. При этом коммутационно-управляющий процессор первого уровня по шинам связи через анализатор процессов вычислений второго уровня посылает сигнал в коммуникационно-управляющий процессор второго уровня. Этот процессор осуществляет поиск необходимого количества рабочих процессоров, расположенных в одном модуле путем опроса сумматоров-вычитателей свободных процессоров. Если такой модуль обнаруживается, все задание передается в коммуникационно-управляющий процессор этого модуля, который его анализирует вышеописанным способом. Если же такого модуля нет с достаточным числом рабочих процессоров, то коммуникационно-управляющий процессор второго уровня анализирует приоритеты выполняемых заданий путем сравнения содержимого регистров 41 и 42 схемой сравнения 43. Если приоритеты выполняемых модулями заданий не меньше, то коммуникационно-управляющий процессор второго уровня через анализатор процессов вычислений третьего уровня и коммуникационно-управляющий процессор третьего уровня, отыскивает модули второго уровня с достаточными ресурсами для их выполнения. Если же в этом случае нет такого модуля и приоритеты выполняемых заданий не меньше, то по сигналу отсутствия требуемых ресурсов, коммутационно-управляющий процессор второго уровня отыскивает модуль с максимальным числом свободных процессоров, куда направляются наиболее связные участки программы, хранящиеся в блоке памяти коммуникационно-управляющего процессора. Остальные участки программы по степени уменьшения связности также посылаются в модули с уменьшающимся числом рабочих процессоров. При решении вопроса о приоритетности выполняемого и поступающего задания, то на любом этапе, если приоритет поступающего задания выше, блок управления коммутационно-управляющего процессора вырабатывает сигнал переписи выполняемого задания, результатов анализа и вычисления во внешнюю память, а ресурсы модуля предоставляются для решения задания с более высоким приоритетом. При загрузке системы через отдельный процессор (вычислительную машину) любого модуля, линейные участки выполняются этим процессором. Дойдя до цикла, рабочий процессор останавливается, передавая задание на распараллеливание цикла через анализатор процессов вычисления, коммутационно-управляющего процессору этого модуля, где и осуществляется распараллеливание цикла вышеописанным способом. Технико-экономические преимущества предлагаемой вычислительной системы состоят в том, что в ней имеется возможность организовать и перестраивать в процессе работы любые связи между рабочими процессорами и другими составляющими ее элементами, как для потока задач, так и при распараллеливании циклов при одновременном уменьшении требований к скоростям информационных обменов с ростом уровня иерархии, обеспечивая тем самым сколь угодно глубокое распараллеливание вычислительных процессов для широкого круга задач с эффективным использованием оборудования и упрощением управления. Эта система позволит эффективно решать многие задачи (математической физики, математической экономики, оптимизации в проектировании и управлении), не имеющие до сих пор эффективного решения. Станет возможным также решение макроэкономических задач со сложными структурами данных на ВЦ коллективного пользования. Экономический эффект от применения настоящего предложения определяется также повышением по крайней мере на порядок производительности при решении широкого круга задач, снижением в 3-4 раза аппаратурных затрат, а также снижением стоимости эксплуатации практически применяемого оборудования за счет его использования в режиме максимальной загрузки. Отметим, что одним из важных преимуществ предлагаемой организации связей и управления вычислительным процессором в многопроцессорной системе является отсутствие необходимости запоминания и восстановления состояний процессоров (рабочих и управляющих) при описанных выше прерываниях и передачах управления. Предлагаемый принцип распределения работы между отдельными рабочими микро-ЭВМ и организации связей между ними напоминает организацию современного массового и притом быстро перенастраиваемого конвейерного производства. Поскольку, в отличие от метода синхронной накачки (pipe-line) распараллеливание работы происходит здесь не на микро-, а на макроуровне, этот принцип назван нами принципом настраивающегося макроконвейера.
Формула изобретения
1. ВЫЧИСЛИТЕЛЬНАЯ СИСТЕМА, содержащая вычислительные машины, коммуникационно-управляющие процессоры, распределенные по уровням иерархии, и внешние устройства, отличающаяся тем, что, с целью повышения гибкости системы, снижения требований к скоростям информационных обменов повышения коэффициента использования оборудования, в нее введены анализаторы процессов вычислений по числу вычислительных машин и коммуникационно-управляющих процессоров, причем каждая вычислительная машина соединена информационной и управляющей шинами с соответствующим анализатором процессов вычислений, соединенным информационной и управляющей шинами с соответствующим комумникационно-управляющим процессором первого уровня, а каждый коммуникационно-управляющий процессор каждого уровня иерархии через соответствующий анализатор процессов вычислений соединен с соответствующим коммуникационно-управляющим процессором соседнего более высокого уровня, причем каждый коммуникационный процессор соединен шиной связи с соответствующим внешним устройством. 2. Система по п. 1, отличающаяся тем, что каждый анализатор процессов вычислений содержит четыре группы регистров, регистр сдвига, три коммутатора, пять схем сравнения, счетчик, два сумматора-вычитателя, сумматор, шесть регистров, группу триггеров, две группы коммутаторов, дешифратор, два элемента ИЛИ, элемент И, причем входы регистров первой и второй групп и всех шести регистров соединены с информационной шиной анализатора, соединяющей анализатор с коммуникационно-управляющим процессором более высокого уровня иерархии, выходы регистров первой, второй и третьей группы соединены с информационной шиной, соединяющей анализатор с коммуникационно-управляющим процессором более низкого уровня иерархии или с вычислительной машиной, группа входов первого сумматора-вычитателя, первые входы первого коммутатора, триггеров группы, входы регистров третьей группы соединены с управляющей шиной, соединяющей анализатор с коммуникационно-управляющим процессором более низкого уровня иерархии или с вычислительной машиной, выходы триггеров группы соединены с входами соответствующих регистров четвертой группы и соответствующих коммутаторов первой и второй групп, выходы коммутаторов первой и второй групп соединены с соответствующими входами соответствующих регистров третьей группы, выход одного из регистров первой группы соединен с управляющими входами коммутаторов первой группы, выход одного из регистров второй группы соединен с управляющими входами коммутаторов второй группы, выходы регистров четвертой группы с группой входов первого коммутатора, выходы регистра сдвига соединены с вторыми входами триггеров группы, выходы которых через последовательно соединенные второй коммутатор и первый элемент ИЛИ соединен с управляющим входом первого сумматора-вычитателя, выходы которого и первого регистра соединены с входами первой схемы сравнения, первый выход которой соединен с первыми входами элемента И и третьего коммутатора, второй и третий входы которого соединены с вторым выходом первой схемы сравнения, первый выход первого коммутатора через второй сумматор-вычитатель соединен с первыми входами второй и третьей схем сравнения, вторые входы которых соединены с выходами соответственно второго и третьего регистров, первый выход второй схемы сравнения соединен с вторым входом элемента И и четвертым входом третьего коммутатора, пятый и шестой входы которого соединены с вторым выходом второй схемы сравнения, выход третьей схемы сравнения соединен с первым входом второго элемента ИЛИ и с вторым входом первого коммутатора, второй выход которого через сумматор соединен с первым входом четвертой схемы сравнения, второй вход которой и первый вход дешифратора соединены с выходом четвертого регистра, выход дешифратора соединен с первым входом счетчика, третьим входом первого коммутатора, управляющим входом второго коммутатора и вторым входом второго элемента ИЛИ, выход которого соединен с входом регистра сдвига, выходы пятого и шестого регистров соединены с входами пятой схемы сравнения, выходы четвертой схемы сравнения соединен с вторыми входами счетчика и дешифратора, выходы счетчика, первого элемента ИЛИ, элемента И, третьего коммутатора и пятой схемы сравнения соединены с управляющей шиной, соединяющей анализатор с коммуникационно-управляющим процессором более высокого уровня иерархии.РИСУНКИ
Рисунок 1, Рисунок 2MM4A Досрочное прекращение действия патента Российской Федерации на изобретение из-за неуплаты в установленный срок пошлины за поддержание патента в силе
Номер и год публикации бюллетеня: 36-2000
Извещение опубликовано: 27.12.2000
