Концепция многооперандной обработки

Размещено на http://www.allbest.ru/

КОНЦЕПЦИЯ МНОГООПЕРАНДНОЙ ОБРАБОТКИ

Гамаюн В.П.

Институт кибернетики имени В.М.Глушкова НАНУ, г. Киев, Украина

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

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

* отсутствие средств и способов параллельных вычислений, пригодных для решения любых задач;

* сложность оперативного управления параллельным процессом и др.

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

Одним из факторов, который определяет снижение производительности, является реализация обработки на операционных элементах (ОЭ) с бинарной пропускной способностью по данным.

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

На этапах развития средств вычислительной техники объекты обработки изменялись от разрядов, байтов до вектора, матрицы, массива, данных циклов. Следующими структурными единицами обработки (СЕО) могут быть данные ветвей алгоритмов, данные участков программ, данные всей программы. бинарный пропускной алгоритмический операционный

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

В работе [3] выделяется определенный род вычислений - интегральные вычисления, когда исходными данными в алгоритме является множество объектов (множество данных различной структуры), а результатом - одно число.

Следует отметить, что большинство вычислений - интегральные. Множество задач могут иметь несколько ветвей, пересекающихся на конечной стадии решения либо не пересекающихся вовсе - параллельные вычисления. Однако каждая из параллельных ветвей представляет интегральное вычисление. Имеется также множество параллельных вычислений с коротким потоком операндов. Для таких задач применяются матричные, систолические, транспьютерные и другие параллельные системы, успешно реализующие задачи с естественным параллелизмом почти с пиковой производительностью [1,2].

Рост производительности при увеличении длины операндов наблюдается в векторных, векторно-конвейерных ЭВМ [1,2]. Однако при этом применяются бинарные ОЭ, и сокращение временных затрат осуществляется за счет уменьшения накладных расходов для более большего потока данных.

Таким образом, в развитии структур и методов обработки можно выделить тенденции, определяющие следующий эволюционный этап:

* интегральные потоки вычислений;

* подходы, вытекающие из требований производительности;

* обеспечение эволюционных шагов в стратегии изменения типов структурных единиц обработки;

* обеспечение обработки ряда команд, составляющих некоторое интегральное вычисление, оператор;

* применение специального арифметико-алгоритмического базиса;

* учет технических решений, применяемых в решении ряда прикладных проблем.

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

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

В настоящее время для построения высокопроизводительных ЭВМ и систем наиболее распространены параллельная и конвейерная концепции. Каждая из них является воплощением подхода повышения производительности путем совмещения выполнения операций [2]. Если при параллельной концепции функция обработки многократно повторяется аппаратурными средствами, то при конвейерной функция обработки разделяется на ряд подфункций, каждая из которых реализуется в ступени конвейера. На недвухместном операционном элементе реализуется функция обработки, соответствующая при традиционном способе обработки нескольким операциям (командам), выполняемым над тем же потоком данных. Другими словами, происходит объединение функций обработки на многооперандном операционом элементе.

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

Гипотеза о многооперандности операционного элемента предполагает его описание в виде модели "черного ящика" со следующими функциями:

пропускная способность по входу - многооперандный входной поток данных;

интегрированный результат, т.е. единичный поток выходных данных;

реализуемая многооперандная операция определяет преобразование, соответствующее операции/команде или некоторому интегрированному управляющему воздействию над многооперандным входным потоком данных.

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

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

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

Введем основные определения компонент вычислительного процесса на многооперандных структурах.

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

Многооперандный поток может быть как упорядоченным, так и неупорядоченным; это свойство означает, что расположение операнда имеет или не имеет значения.

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

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

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

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

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

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

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

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

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

Таким образом, можно утверждать, что применение многооперандных операционных элементов в вычислительных структурах является основой сокращения промежуточных результатов и, следовательно, упрощения и сокращения потокообмена в структуре, а также переходом к макрооператорному типу обработки. При таком типе обработке МНОЭ реализует некоторую интегрированную управляющую компоненту при преобразовании многооперандного потока данных. Если макрооператор заменяет несколько управляющих конструкций по преобразованию/обработке данных, то при таком подходе происходит сокращение количества операций (их заменяют одним макрооператором) за счет структурных методов, что отличается от традиционных подходов. Известно, что разработка так называемых быстрых алгоритмов явилась следствием факторизации матриц, т.е. алгебраических методов [1,2]. Предлагаемый подход является структурным . Другими словами, при решении задачи количество операций, представленное в исходной постановке, может быть сокращено при погружении алгоритмической структуры в структуру многооперандную.

Многооперандная команда может быть сформирована при определенных условиях - условиях многооперандной обработки:

наличие интегрального типа вычислений;

наличие возможностей объединения инструкций (команд) в одну управляющую конструкцию.

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

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

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

Если программа содержит M команд, обеспечивающих преобразование V обьема данных, то при условии, что используется каждый полученный результат и преобразование происходит на вычислительной структуре с бинарной пропускной способностью, результат работы программы будет получен не ранее чем *log 2 V шагов. При увеличении пропускной способности s(s>2) количество шагов уменьшается с ростом s и равно *logs V. Предельное значение при s=V равно logs V =1.

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

Литература

1. Супер Э В М. Аппаратная и программная реализация /Под. ред. С.Фернбаха: Пер. с англ.- М.: Радио и связь, 1991. -320 с.:ил.

2. Коугли П.М. Архитектура конвейерных ЭВМ. - М.: Радио и связь, 1985 - 358 с.

3. Карцев М.А., Брик В.А. Вычислительные машины и синхронная арифметика. - М.: Радио и связь, 1981. - 360 с.: ил.

4. Гамаюн В.П. О развитии многооперандных вычислительных структур // УСиМ. - 1990. - N 4. - С. 31 - 33.

5. Гамаюн В.П. Организация обработки в многооперандных вычислительных структурах. - Киев,1996. - 20 с. - (Препр./НАН Украины. Ин-т кибернетики им.В.М.Глушкова; 96-3).

Размещено на Allbest.ru