Pipelining of combinational circuits.pdf Повышению производительности систем обработки информации всегда уделялось большое внимание. Одним из способов повышения производительности является применение структуры конвейерного типа, который имеет ещё название «трубопровод» (перевод с англ. слова «pipeline») [1]. Подобную структуру образуют несколько независимых процессоров, соединённых между собой последовательно. При построении систем цифровой обработки сигналов в режиме реального времени широкое распространение получил систолический принцип организации вычислений [2]. Информация в систолическом процессоре распространяется по конвейеру подобно тому, как пульсирует кровь при сокращении систолы сердца. В данной работе излагается попытка найти способ повышения быстродействия путем конвейеризации многоуровневой комбинационной схемы, построенной на основе СБИС. В многоуровневой схеме устройства задержка складывается из задержек элементов самой длинной цепочки. Пусть на вход комбинационной схемы поступает последовательность р наборов двоичных сигналов. Если Т — время задержки схемы, то период смены сигналов не может быть меньше T. Время реакции устройства на данную последовательность в этом случае не меньше грТ. Разобьём схему на k каскадов (С, C2,..., Ck), и если тс — время задержки самого медленно действующего каскада, то Т ^ ктс. На выходы каждого каскада поставим элементы задержки (триггеры D), пропускающие сигналы с выходов каскада по сигналу синхронизации. Этот же сигнал синхронизации определяет период смены сигналов на входе устройства, который должен быть не меньше суммы двух задержек: задержки тс и задержки td элемента D (Tclock ^ тс+td). Теперь время реакции устройства на упомянутую последовательность равно (к + р)Tdock. Нижняя граница длины р последовательности наборов двоичных сигналов на входе устройства, при которой имеет место ускорение обработки сигналов, определяется неравенством (к + р)тС!ОСк < 'рТ. Учитывая нижнюю границу периода следования сигналов синхронизации Tclock, получим kTclock . к(тс + Td ) р > 7F,- ^ Т — Tclock Т — тс — TD Заданную схему требуется разбить на заданное число к каскадов, чтобы обеспечить по возможности максимальное быстродействие при описанном конвейерном режиме. В качестве модели схемы используется бесконтурный орграф G = (V,A). Его вершины из множества V представляют логические элементы и входные полюсы схемы, а дуги из множества A показывают направления сигналов от выходов одних элементов к входам других. Каждой вершине v Е V приписан вес т(v), представляющий задержку соответствующего элемента. Вершины, соответствующие входам схемы, имеют вес 0. Сформируем последовательность слоев L\, L2, ..., Lm, представляющую собой упорядоченное разбиение множества вершин V орграфа G с таким свойством, что если вершина v принадлежит полуокрестности исхода N + (u) вершины u, то эти вершины находятся в разных слоях и слой, содержащий вершину u, предшествует в этой последовательности слою с вершиной v (не обязательно непосредственно). Если длины путей от входов схемы к её выходам различны, то такое разбиение не является единственным. Следует выбрать такой вариант разбиения на слои, чтобы сумма весов всех слоев была по возможности минимальной. Под весом слоя понимаем максимум весов вершин, принадлежащих данному слою. Можно выделить два типа вершин орграфа G. К одному типу отнесем вершины, которые лежат на самых длинных путях в орграфе G. Они строго распределяются по слоям и не могут менять своё положение. Их назовём неподвижными. Положение в слоях других вершин, которые назовём подвижными, можно менять в определённых пределах, скажем, от слоя Li до слоя Lr (l < r). Эти пределы устанавливаются с помощью алгоритма, подобного алгоритму топологической сортировки [3]. Для окончательного распределения вершин по слоям так, чтобы сумма весов сло-ёв была по возможности минимальной, предлагается следующий способ. Удалив из орграфа G неподвижные вершины вместе с инцидентными им рёбрами, получим орграф H, в каждой компоненте которого выделим вершину с максимальным весом. Эту вершину поместим в один из допустимых для неё слоёв с максимальным весом. Границы положения вершин при этом изменятся и некоторые вершины из подвижных перейдут в неподвижные. Дальнейшее распределение по слоям можно вести для каждой компоненты орграфа H описанным способом. Все пути в орграфе приводятся к единой длине путем добавления новых вершин с нулевым весом. Каждому из слоёв соответствует множество значений веса, приписанных вершинам, принадлежащим данному слою. Максимальное значение веса в слое представляет собой задержку прохождения сигнала в этом слое. Заданную комбинационную схему надо разбить на заданное число каскадов с минимизацией задержки в самом медленно действующем каскаде. Каждый каскад представляет собой упорядоченное множество слоёв. Рассматриваемая задача теперь сводится к следующему. Дана последовательность положительных чисел (a\,a2,... ,an). Требуется её разбить на заданное число к отрезков Bi, B2} ..., Bk, где Bi = (am_1+i,..., am), i =1, 2,... ,к, no = 0, nk = n. При этом надо, чтобы величина max{Sl, S2,..., Sk}, где Sj, = ani_1+l + ... + ani, была по возможности минимальной. Элементы Bi соответствуют каскадам в заданной схеме. Предлагается алгоритм получения решения данной задачи, близкого к оптимальному.

Скачать электронную версию публикации