Раздел: Документация

0 ... 27 28 29 30 31 32 33 ... 78

устойчивых систем. Не все из ранее известных результатов можно применить к этой ситуации. Рассмотрим хорошо известный закон Прайса [8]: Y = (1 +DA/m)~m,

где Y - доля выхода годных кристаллов; D - плотность дефектов, А - эффективная площадь кристалла; т - число факторов, вызывающих появление дефектов, определяется в основном числом этапов изготовления.

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

1)на нижнем уровне изготовление каждого узла или процессорного элемента подчиняется закону Прайса, что дает определенную единичную плотность f дефектов (нефункционирующих процессоров);

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

Во-вторых, в известных неотказоустойчивых системах выход годных равен вероятности того, что в области А дефекты отсутствуют. Для отказоустойчивой системы параллельных процессоров, такой как предлагаемая далее, это определение не выполняется. В системах- со структурной отказоустойчивостью можно допустить большое число неисправных элементов, вплоть до 0(N) из N процессорных элементов, если распределение этих элементов оптимально. Как определено с помощью двухуровневой модели, степень выхода годных дчя систем со структурной отказоустойчивостью зависит от локального распределения дефектов. Если система будет функционировать с к или меньшим числом смежных дефектов, то общая доля выхода годньгх в процессе производства равна вероятности того, что число смежных дефектов кристалла нигде не превышает к : У=Рг (дефекты встречаются не более чем в к смежных процессорах).

10.2. СТРУКТУРНАЯ ОТКАЗОУСТОЙЧИВОСТЬ

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

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

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

Пример. LU-разложение. На рис. 10.2 показано применение этой техники к алгоритму LU-разложения [19]. Если процессор (0,2) неисправен, то дефектная линия вычислений, которые должны выполняться этим процессором, может быть выполнена ремонтным процессором (-1,1). Ремонтная линия является структурной ремонтной линией, т.е. во время выполнения "ремонтных" вычислений никаких других вычислений быть не должно. Алгоритм LU-разложения имеет структурную отказоустойчивость уровня два. На рис. 10.2,в, г показаны локальный граф ошибок и локальное преобразование связей при отказе линии связи у дефектного процессора. В этом случае для изменения маршрута вычислений требуется выполнить три шага за цикл.

10.3. АНАЛИЗ ВЫХОДА ГОДНЫХ

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

1)d - размерность систолической матрицы;

2)п - число дефектных процессоров в системе;

3)/ - единичная функция плотности дефектов (одна и та же для всех дефектов);

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

можно показать, что

W Hr.k)fг

П=1 I(-ir+1AU<m) •• /Ас, - АИСг„

r=l 1=1Jcri J

где Gri - графы (содержащие v (Сгг-) вершин) путей, в которых тройки пар соседних дефектных процессоров имеют общий дефектный процессор; t (г, к) - число таких графов для фиксированного значения/- в серии включений-исключений; Nrik(m) - комбинаторный коэффициент.

---

Номера означают моменты в которые производятся Вычисления

Гексагональная систолическая структура

Исправление вычислений происходит в относительный момент времени О

д)

г)

6}

-3Vl2«I0~6P™e МГОРИ™а -разложения для введения структурной № а- исходное итерационное пространство для Ш-разложения- Я

иТеРационного пространства; g локальный граф%™тов г~°™б*>*™™

зеи,позвоЛян>Щее не увеличивать полосу пропусканиГсзей~ РаСПреДе~ свй"

ОЛ

I 0,3

I

Г2

Ox о *

х -змееОидная структура уровень

отказоустойчивости г о -линейная структура уровень

отказоустойчивостиг + - линейная структура омвлм

отказоустойчивости!

х о

x

о

x

о

50

100

150

200

Число процессорных элементов

250

Рис. 10.3. Плотность распределения дефектов в зависимости от числа процессорных элементов (на кристалле) при значении выхода годных 0,5

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

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

В линейной змеевидной структуре (см. рис. 10.1, б) допускается, что процессор в одной строке может исправлять работу процессора в соседней строке.

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

Результаты моделирования для сетей, содержащих от 16 до 256 процессоров, приведены на рис. 10.2. Этот рисунок показывает распределение допустимой плотности дефектов для общего уровня выхода годных 0,5.

Метод структурной отказоустойчивости сравнивался с методом изготовления СБИС на одной пластине (см. список литературы), в особенности для змеевидного линейного расположения элементов. Например, на рис. 10.3 изображена матрица, содержащая 8X8 процессоров со случайным расположением дефектных элементов с плотностью 29%, соответствующей уровню выхода годных, равному 71 %. При простом алгоритме, предназначенном для интеграции на уровне целых пластин, практический выход годных 50% достигается соединением, показанным на рис. 10.1,а.

Систолическая матрица с уровнем структурной отказоустойчивости 1, расположенная змеевидным способом с назначением "ремонтных" процессоров, показанным на рис. 10.1,6", дала работоспособную систему с 71 %-ным выходом годных. По своей сути в методе интеграции на уровне полупроводниковой пластины используется аппаратная избыточность, тогда как в методе структурной отказоустойчивости - временная, поскольку систолическая матрица будет работать с половинной скоростью. (Были развиты и более сложные методы [4], но в них также используется некоторая временная избыточность.)

Данное обсуждение касалось только независимых точечных дефектов; в интегральных же микросхемах проявляются дефекты и других типов: линейные, группы точечных дефектов и дефектные области. Кроме того, наблюдается значительное радиальное изменение плотности дефектов [5]. Из-за температурного градиента при изготовлении, коробления фотошабло-

a

8

7

Свободные циклы, привязанные к 6 точкам итерационного пространства 5

J г

пот

---

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

10.4. ЗАКЛЮЧЕНИЕ

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

СПИСОК ЛИТЕРАТУРЫ

[J") R. С. Aubusson and I. Catt, "Wafer Scale Integration-A Fault Tolerant Procedure,"

IEEE J. Solid-State Circuits, SC-/3(3):339-344 (June 1978). [2] Y. Egawa, T. Wada, Y. Ohmori, N. Tsuda, and K. Masuda, "A 1-Mbit Full-Wafer MOS

RAM," IEEE J. Solid State Circuits, CS-i5(4):677-686 (Aug. 1980). [3] D. Fussell and P. Varman, "Fault-Tolerant Wafer-Scale Integration for VLSI," 9th

Symp. Comput. Architecture, 1982, pp. 190-198.

[4] D. Gajski and A. H. Sameh, "A WSI-Multiprocessor for Iterative Algorithms," Proc. GOMAC-82, Nov. 1982.

[5] A. Gupta, W. A. Porter, and J. W. Lathrop, "Defect Analysis and Yield Degradation of Integration Circuits," IEEE J. Solid-State Circuits, SC-9-96- 103 (June 1974).

[6] R. M. Lea and M. Sreetharan, "VLSI Distributed Logic Memories," Proc. Caltech Conf. Very Large Scale Integration, Caltech Computer Science Department, Jan. 1979.

[7] Z. A. Melzak, Companion to Concrete Mathematics. Wiley, New York, 1973.

[8] J. E. Price, "A New Look at Yield of Integrated Circuits," Proc. IEEE, 5#:1290 1291 (Aug. 1970).

ДЕКОМПОЗИЦИЯ БОЛЬШИХ МАТРИЦ ДЛЯ ОГРАНИЧЕННЫХ СИСТОЛИЧЕСКИХ СТРУКТУР

Д. Хел/iep1

11.1 ВВЕДЕНИЕ

В этой главе будет показано, каким образом проектирование систолических матричных процессоров и структур данных может быть адаптировано для матричных вычислений, которые не могут быть реализованы за один прогон данных через систолическую структуру. Обычно систолические структуры проектируются для вычислений за один проход. Покажем, как разбиение данных и их маршрутизация делают эту проблему разрешимой. Полагаем, что читатель знаком с основными работами по систолическим матричным процессорам, в частности с работами 13,8, 11, 12, 19], и имеет представление о конвейерных векторных вычислениях (например, [5, 9]). Другие специализированные устройства, предназначенные для СБИС-исполнения, могут быть рассмотрены аналогичным образом.

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

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

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

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

1 Университет шт. Пенсильвания.

0 ... 27 28 29 30 31 32 33 ... 78