Новосибирский государственный университет

Факультет информационных технологий

ICT SBRAS

Словарь терминов в коллекции "Вычислительные системы"

Классификация Шнайдера

Классификация Шнайдера: конкретизация класса SIMD, основанная на идее - выделения этапов выборки и непосредственно исполнения в потоках команд и данных.

В 1988 году Л.Шнайдер (L.Snyder) предложил новый подход к описанию архитектур параллельных вычислительных систем, попадающих в класс SIMD систематики Флинна. Основная идея заключается в выделении этапов выборки и непосредственно исполнения в потоках команд и данных. Именно разделение потоков на адреса и их содержимое позволяет описать такие ранее «неудобные» для классификации архитектуры, как компьютеры с длинным командным словом, систолические массивы и целый ряд других.

Потоком ссылок (reference stream) S некоторой ВС называется конечное множество бесконечных последовательностей пар:
S = {(a1<t1>)(a2<t2>)...,
(b1<u1>)(b2<u2>)...,
(c1<v1>)(c2<v2>)...},
где первый компонент каждой пары - это неотрицательное целое число, называемое адресом, второй компонент - это набор из n неотрицательных целых чисел, называемых значениями, причем n одинаково для всех наборов всех последовательностей. Например, пара (b2<u2>) определяет адрес b2 и значение <u2>. Если значения рассматривать как команды, то из потока ссылок получается поток команд I; если же значения интерпретировать как данные, то соответствующий поток - это поток данных D.

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

Пусть S произвольный поток ссылок. Последовательность адресов потока S, обозначаемая Sa, - это последовательность, чей i-й элемент - набор, сформированный из адресов i-х элементов каждой последовательности из S:
Sa = <a1b1...c1>, <a2b2...c2>,...
потока S, обозначаемая Sv, - это последовательность, чей i-й элемент - набор, образованный слиянием наборов значений i-х элементов каждой последовательности из S:
Sv = <t1u1...v1>, <t2u2...v2> ,...
Если Sx - последовательность элементов, где каждый элемент - набор из n чисел, то для обозначения «ширины» последовательности будем пользоваться обозначением: w(Sx) = n.
Из определений Sa, Sv и w сразу следует утверждение: если S - это поток ссылок со значениями из n чисел, то w(Sa) = |S| и w(Sv) = n|S|, где |S| обозначает мощность множества S.

Каждая пара (I, D) с потоком команд I и потоком данных D называется вычислительным шаблоном, а все компьютеры разбиваются на классы в зависимости от того, какой шаблон они могут исполнить. В самом деле, компьютер может исполнить шаблон (I, D), если он в состоянии:

Если все эти условия выполнены, то компьютер может быть описан следующим образом: Iw(Ia)w(Iv)Dw(Da)w(Dv).

Классическая последовательная машина согласно классификации Флинна попадает в класс SISD, следовательно |I| = |D| = 1. Используя утверждение 1, получается, что w(Ia) = w(Da) = 1. Из-за того, что в подобного рода компьютерах команды декодируются последовательно, следует равенство w(Iv) = 1, а последовательное исполнение команд дает w(Dv) = 1. Поэтому описание однопроцессорной машины с фон-неймановской архитектурой будет выглядеть так: I1,1D1,1.

Теперь рассмотрим две машины из класса SIMD: Goodyear Aerospace MPP и ILLIAC IV, причем не будем принимать во внимание разницу в способах обработки данных отдельными процессорными элементами. Единственный поток команд означает |I| = 1 для обеих машин. По тем же соображениям, использованным только что для последовательной машины, для потока команд получается равенство w(Ia) = w(Iv) = 1. Для доступа к операндам устройство управления (УУ) MPP рассылает один и тот же адрес всем процессорным элементам (ПЭ), поэтому в этой терминологии MPP имеет единственную последовательность в потоке данных, т.е. |D| = 1. Однако затем выборка данных из памяти и последующая обработка осуществляется в каждом ПЭ, поэтому w(Dv) = 16384, а вся система MPP может быть описана так: I1,1D1,16384.

В ILLIAC IV УУ, так же, как и в MPP, рассылает один и тот же адрес всем ПЭ, однако каждый из них может получить свой уникальный адрес, добавляя содержимое локального индексного регистра. Это означает, что |D| = 64 и в системе присутствуют 64 потока адресов данных, определяющих одиночные потоки операндов, т.е. w(Da) = w(Dv) = 64. Суммируя сказанное, описание ILLIAC IV выглядит так: I1,1D64,64.

Для более четкой классификации Шнайдер вводит три предиката для обозначения значений, которые могут принимать величины w(Ia), w(Iv), w(Da) и w(Dv):В этих обозначениях, например, фон-неймановская машина принадлежит к классу IssDss. Несмотря на то, что и c и m в принципе не имеют определенной верхней границы, они отражают разные свойства архитектуры компьютера. c предполагает жесткие ограничения сверху со стороны аппаратуры, и соответствующий параметр не может быть значительно увеличен относительно простыми средствами. Примером может служить число инструкций, упакованных в командном слове VLIW компьютера. С другой стороны, описатель m используется тогда, когда обозначаемая величина может быть легко изменена, то есть другими словами, компьютер по данному параметру масштабируем. Например, относительная простота в увеличении числа ПЭ в системе MPP является основанием для того, чтобы отнести ее к классу IssDsm. Конечно же, различие между c и m в достаточной мере условное и, как правило, порождает массу вопросов. В частности, как описать машину, в которой процессоры связаны через общую шину? С одной стороны, нет никаких принципиальных ограничений на число подключаемых процессоров. Однако каждый дополнительный процессор увеличивает загруженность шины, и при достижении некоторого порога подключение новых процессоров бессмысленно. Как описать такую систему, c или m? Автор оставляет данный вопрос открытым.

На основе указанных предикатов можно выделить следующие классы компьютеров:Достаточно ясно, что не нужно рассматривать все возможные комбинации описателей s, c и m, так как архитектура реальных компьютеров накладывает ряд вполне разумных ограничений. Очевидно, что число адресов w(Sa) не должно превышать числа возвращенных значений w(Sv), которое компьютер может обработать. Отсюда следуют неравенства: w(Ia) ≤ w(Iv) и w(Da) ≤ w(Dv). Другим естественным предположением является тот факт, что число выполняемых команд не должно превышать числа обрабатываемых данных: w(Iv) ≤ w(Dv).

Подводя итог, можно отметить два положительных момента в классификации Шнайдера: более избирательная систематизация SIMD компьютеров и возможность описания нетрадиционных архитектур типа систолических массивов или компьютеров с длинным командным словом. Однако почти все ВС типа MIMD опять попали в один и тот же класс ImmDmm. Это и не удивительно, так как критерий классификации, основанный лишь на потоках команд и данных без учета распределенности памяти и топологии межпроцессорной связи, слишком слаб для подобных систем.

Литература

Дополнительная:

  1. Воеводин Вл.В. Методы описания и классификации архитектур вычислительных систем / Вл.В. Воеводин, А.П. Капитонова. - М.:Издательство МГУ, 1994. - 79 с. - ISBN 5-211-03355-8.

Ключевые термины:  архитектура вычислительной машины;   процессор;   уровни параллелизма;   классификация флинна;


Контекстный поиск: Задайте образец для поиска:
    

|Список основных тем курса|
   
Федотова Ольга
[SBRAS]

НГУ
ФИТ НГУ
ИВТ СО РАН
© 2012-2024, Новосибирский государственный университет, Новосибирск
© 2004-2024, Институт вычислительных технологий СО РАН, Новосибирск
© 2004-2024, Федотов А.М.
    Дата последней модификации: 14.08.2013