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

ОБЪЕДИНЕННЫЙ ИНСТИТУТ ЯДЕРНЫХ ИССЛЕДОВАНИЙ

Г 3

10-96-467

На правах рукописи УДК 519.688:681.3.012:539.1.05

АЛЕКСАНДРОВ Игорь Николаевич

МЕТОДЫ МОДУЛЯРНОЙ АЛГЕБРЫ И КОНВЕЙЕРНЫЕ ВЫЧИСЛЕНИЯ В ТРИГГЕРНЫХ АЛГОРИТМАХ ЭКСПЕРИМЕНТОВ НА ЬНС

Специальность: 05.13.16 — применение вычислительной техники, математического моделирования и математических методов для научных исследований

Автореферат диссертации па соискание ученой степени кандидата физико-математических наук

Дубна 1996

Работа выполнена в Лаборатории вычислительной техники и автоматизации Объединенного института ядерных исследований, г. Дубна.

Научные руководители: кандидат технических наук

Котов Владислав Михайлович

доктор технических наук Никитюк Николай Михайлович

Официальные оппоненты: доктор физико-математических наук

Иванченко Иосиф Моисеевич

кандидат технических наук Сытин Александр Николаевич

Ведущая организация: Московский радио-технический институт

Российской Академии наук

Защита диссертации состоится " " Ж ^АР ^(Л _ 1997 года в

мин. на заседании Диссертационного совета Д047.01.04 при Лаборатории вычислительной техники и автоматизации Объединенного института ядерных исследований по адресу: 141980, г.Дубна Московской области.

С диссертацией можно ознакомиться в библиотеке ОИЯИ.

Автореферат разослан " ^^ " Ь^Р'Х._199^г.

/

Ученый секретарь Диссертационного совета кандидат физико-математических

<* г. Иванченко наук Зинаида Мироновна

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

Научная новизна. Предлагаемые в диссертационной работе методы являются новыми и расширяют область применения аппарата модулярной алгебры и новых технологий СБИС на потоковую обработку данных в системах сбора и обработки физических событий.

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

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

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

Практическая ценность. Предложенные методы и алгоритмы использованы при вычислении поперечного импульса мюона и создании полного алгоритма обработки для прототипа мюонного триггера второго уровня в автономном режиме установки ATLAS LHC. На основе предложенных методов и алгоритмов разработано программное обеспечение для синтеза гибких логических модулей, получены схемы конкретных устройств. Синтезирован переключатель с пропускной способностью 1.6 Гбит/сек для использования в составе прототипа. Показана возможность создания нового типа распределенной памяти, использующей чисто комбинационные операции в ее активной части. Коммутаторы могуг применяться в качестве базовых элементов в коммутационных сетях.

Апнробацня работы. Основные результаты работы доклыдывались на международных конференциях: "Аналитические вычисления на ЭВМ и их применение в теоретической физике" ( Дубна, ОИЯИ, 1985г.), "The Rhine Workshop on Computer Algebra" (Карлсруэ, Германия, 1994г.), "Real Time Data'94" (Дубна, ОИЯИ, 1994г.), "ESONE Real Time Data'95" (Варшава, Польша, 1995 г.); на научных семинарах Лаборатории вычислительной техники и автоматизации, Лаборатории ядерных проблем; докладывались на совещаниях "ATLAS week" (ЦЕРН, Женева, Швейцария).

Публикации. По материалам диссертации опубликовано 10 печатных работ, список которых приведен в конце автореферата.

Объем н структура диссертации. Диссертация состоит из введения, трех глав, разбитых на параграфы, заключения, приложения, списка литературы из 70 наименований. Объем основного текста диссертации - 100 страниц, включая 22 рисунка.

СОДЕРЖАНИЕ РАБОТЫ

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

Создаваемая на LHC установка ATLAS, предназначенная для поиска редких физических событии, будет представлять из себя сложнейшую систему тородоидаль-ной формы весом 7000 тони, радиусом 11 метров и длиной 42 метра, содержащую только в мюопном детекторе сотни тысяч каналов регистрации. Планируемая частота возникновения событии на LUC равна 40 МГц, то сеть каждые 25 не из детектора будет поступать на обработку до I Мгб данных. Анализ таких объемов информации невозможен без работы тригтерной системы, задачей которой является предвари тельный отбор полезных физических событий в режиме реального времени на основе упрошенных алгоритмов обработки данных. Диссертационное исследование проводилось в рамках работ по созданию мюониой триггерной системы установки ATLAS, предназначенной для поиска треков в мюонпом детекторе на управляемых трубках высокого давления (MDT) и измерения поперечного импульса мюона. Триггерная система ATLAS включает в себя три уровня. На первом уровне обрабатываются данные, поступающие из всех областей детектора с частотой 40 Мгн, общее время обработки 1-2мкс. На этом уровне активно используются гибкие логические устройства, работающие параллельно в конвейерном режиме. Помимо жестких требовании на быстродействие, обязательным свойством таких устройств должна бып. гибкость, то есть возможность настройки их в зависимости от изменения входных параметров. В связи с этим в диссертационном исследовании была поставлена и решена задача разработки алгоритмов для синтеза быстрых и гибких универсальных логических модулей.

Целыо обработки данных на первом уровне триггера является поиск так называемых областей интереса (ROI - region of interest), то есть параметров rex областей детектора, и которых обнаружены признаки появления полезных физических событий. Ожидаемая частота событий на выходе первого уровня составляет величину порядка lOOKni, поэтому продолжительность обработки на втором уровне триггера уже-несколько миллисекунд. На втором уровне триггера обрабатываются данные только из ROI, параметры которых получены па предыдущем уровне. При этом во шикают сложные задачи коммутации данных, так как они находятся в различных буферах ввода - вывода. В одном и том же локальном процессоре в разное время должны обрабатываться данные из произвольного буфера или заданного множества таких буферов. При выборе коммутационных средств для LHC будут широко использоваться промышленные разработки средств коммутации, хотя в отдельных блоках систем сбора и обработки событий предполагается использование специальных разработок. Одним из основных элементов всех протоколов коммутационной среды является

переключатель. Известны 3 основных принципа построения таких коммутирующих устройств: многокаскадные коммутаторы на основе '2x2 переключателя, использование двухпортовых памятей и мультиплексирование. Все эти подходы имеют свои преимущества и недостатки. Например, с ростом п при построении п х п переключателей на базе каскадов переключателя 2x2 существенно увеличиваются задержки, при мультиплексировании необходим адрес передатчика информации, что не всегда удобно, в двухпортовой памяти объем управляющей электроники растет по степенному закону при увеличении шкалы коммутации. Поэтому исследования в данной области продолжаются, и вопрос о выборе конкретных технологий для применения в экспериментах lia LHC остается открытым. В данном диссертационном исследовании предложен метод построения адаптивного комбинаторного переключателя, использующего в схеме коммутирования только адреса приемников, таким образом, отсутствует необходимость подавать на входы переключателя адреса источников передачи данных.

Одной из основных функций мюоного триггера второго уровня является опознание трека мюона. Построение параллельных алгоритмов впрямую зависит or специфики данных, поступающих на обработку, то есть от устройства самого мюоиного детектора. Мюонный детектор установки ATLAS строится на основе трубок MDT различной длины (от 2 до 6 метров) диаметром i см. Позиция частицы (в дальнейшем - отсчет) внутри трубки определяется временем дрейфа наведенных электронов к анодной проволочке, расположенной в центре трубки. Существенной особенностью данных является знаковая неопределенность, необходимо определять: с какой стороны от центра трубки дрейфовали электроны, давшие сигнал отсчета в MDT. Трубки MDT слоями компонуются в мюонные камеры, сначала плотно, в шахматном порядке, размещаются по 3 слоя трубок, затем па расстоянии порядка 30-50 см еще по 3 слоя. Формообразующей компоновкой мюонпых камер является тороид. В направлении возрастания радиуса формообразующего тороида располагаются по 3 мюонные камеры: внутренняя - па расстоянии порядка 5 метров от центральной оси детектора, затем средняя и внешняя с зазором порядка 2.5-3 метров между ними. В проекции ф детектор разбит на 8 секторов, длины трубок подобраны в соответствии с этой разбивкой. Вдоль оси 2, совпадающей с главной осыо формообразующего тороида, каждая камера содержит от 30 до 70 трубок в слое. Ожидаемый уровень шумов в мюонном детекторе равен 102 на сгп2.

В первой главе рассмотрены методы и алгоритмы квазисистолической обработки трнгтерных данных для опознания треков в мюонном детекторе ATLAS на основе применения технологии СБИС ALTERA. Квазисистолическими в диссертации названы систолические алгоритмы обработки данных, в которых допускаются глобальные связи между ячейками. Основная идея построения алгоритмов состоит в организации последовательно - параллельных вычислений в регулярной матричной структуре. Такой подход позволяет производить анализ алгоритма для выделения массовых операций с тем, чтобы упростить в первую очередь используемые в этих

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

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

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

гае Л = т^г^; Мк,М1,Мп - количество точек на слоях (плоскостях) к, 1,п\ N -количество всех слоев за исключением опорных плоскостей к и I, по отсчетам на которых строилась аппроксимирующая прямая, для всевозможных индексов ij, где ] - любая плоскость, i - произвольный отсчет на этой плоскости, - время дрейфа, соответствующее выбранному отсчету, = ±1 - знак направления дрейфа, Р,_, -7.-координата центра трубки МОТ, Л, - расстояние до центра плоскости ] (радиус), <т„ - точность измерения положения точки на плоскости п. в по определению интегральной модели имеет вид:

N Л/t М, Л/„

F(To) = Е Е Е Е G[Arg(ToY, ап] (1)

п=1 К=1 А=1 (1=1

Агд(Т0) = Г0[5„п - S» - h(S*k - Su)] - {[Р„„ - Рл;--h(PKk - PM)]/V + W - Sutл, - h(S^tKk - Saiîai]} (2)

Кроме времен дрейфа, все значения используемых в (1)-(2) переменных известны заранее, множественность по каждой плоскости 1,п,к не превышает 6. В каждом цикле ускорителя, равном 25нс, на входе в квазисистолический вычислитель имеется матрица значений времен дрейфа:

( к 1 tl2 tk 2

D =

in,l \

щ2

tl6 tkb

in26

W

\

itnC /

Для множественности отсчетов на слое, равной шести, в силу (1) возникает необходимость осуществления 1296 переборов. Для того, чтобы не производить все операции (2) для каждого набора матрицы й, строится вычиелтель, преобразующий Входные значения из О в матрицу V:

D' =

¥ t' t' llO 46 ni6

l

ni6 1

Здесь

«1-х = + 1) + [SkT0(h + 1) + (Tk - T,)h + Tk - Tn

t',x = SiToh — Sihtix,

С

—Sntnu 4- SnTo,

где Ti — P,/V дня i = k,l,n вычисляются предварительно

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

Таким образом, вычисления по формулам (1)-(2) сводятся к перебору всевозможных значений (t'k,t[,t'„) матрицы D', и вычислению для них Arg{T0) = t'k + t', + t'n, а затем суммированию всех величин G(Arg(T0)). Предлагается реализовать вычисление Arg и G потоковым методом, последовательно выполняя операции:

Шаг 1. РхХ = t[x + t'kx Шаг 2. Нхт = + t'fm Шаг 3. Вычисление |На^х|

Шаг 4. SxXll = ((|tfA„*| - а) < 0) Шаг 5. Суммирование всех 5хЛ/<

Шаг 6. Сравнение с порогом результата шага 5 и в случае его превышения - выдача сигнала о наличии трека для заданных Ти и PS.

Вычисления производятся в регулярной вычислительной структуре, построенной в СБИС ALTERA, с максимальным распараллеливанием выполняемых операций. Способ организации параллельных вычислений, подробно описанный в диссертации, сводится к построению квазисистолического вычислителя в виде матрицы, элементы которой состоят из сгруппированных в тройки сумматоров, реализующих шаги 2 и 3, шаг 1 реализуется в первой колонке матрицы, шаги 5 и 6 - в быстрых счетчиках. Все значения матрицы D' вводятся в вычислитель одновременно параллельным колом. В целях экономии объемов электроники рассмотрена возможность обработки данных последовательно - параллельным кодом, при этом принцип организации вычислений не изменяется, но данные вводятся за три такта работы вычислительной структуры, по два разряда данных за такт, начиная с младших, при этом в вычислениях учитывается значение переноса в операциях суммирования из предыдущего такта. Показано, что при разрядности данных, равной шести, обработка всех разрядов данных в потоковом режиме производится с частотой работы ускорителя, рассмотрены различные реализации этого подхода в СБИС ALTERA.

В параграфе 1.3 описывается построение параллельного алгоритма для триггера второго уровня. В данном случае считается, что информация о времени рождения события уже известна, кроме того, на первом уровне выделены ROI. Аппроксимирующей трек кривой в r/z-проскции является парабола, так как учитываются данные, поступившие со всех трех камер детектора. После фиксации слоев р. к и I в качестве опорных, то есть тех, по отсчетам на которых определяются параметры аппроксимирующей трек параболы, задача сводится к определению истинности условия F > Fthrc!ihM для всех возможных парабол, проходящих через точки отсчетов на опорных плоскостях, где для каждой параболы

N Л/„

F = £VG[.4r<H,

и = 1 m— 1

Ar i 1 с-сли | zm - А-r'f,- В-rn-С\< a [ 0 иначе

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

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

Основная идея построения алгоритма следующая:

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

2. На втором уровне алгоритма для каждого указанного в пункте 1 отсчета ищется точка пересечения траектории частицы с прямой, проходящей через центр слоя трубок МОТ, которому принадлежит трубка с отсчетом. Далее в вычислениях предлагается использовать только эти вновь полученные координаты точек. Таким образом, для каждого слоя г-координата любого отсчета на этом слое становится константой. Как и на первом уровне параметры любой параболы становятся зависимыми только от /.-координат отсчетов, причем зависимость является линейной, что упрощает вычисления.

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

В параграфе показана реализация данной идеи построения алгоритма, более подробно описана та часть алгоритма, которая реализует опознавание трека на

уровне центров трубок, так как именно в этой части сосредоточены наиболее массовые операции. После упрощений массовые вычисления сведены к подсчету выражений вида 2„ = Kin ■ z¡ + К2„ ■ Zp, где коэффициенты К\п и зависят только от номера слоя и подсчитываются заранее. Предложено проводить массовые вычисления параллельно - последовательным кодом. Трек опознается за 247 тактов работы квазисистолического вычислителя, построенного на базе СБИС FLEX ALTERA, за время порядка 5мкс при множественности отсчетов на слое внутри ROI, равной четырем, то есть даже при условии возникновения шумов, уровень которых выше ожидаемого.

В главе 2 описаны разработаные методы и алгоритмы для построения гибких логических модулей па основе переключательных функций в полях Галуа GF(2m). Модули предназначены для использования в триггсрных системах. Несмотря иа то, что в диссертационном исследовании данные модули предложено использовать в мю-онном триггере, задача разработки алгоритмов для получения логических выражений, являющихся основой для синтеза универсальных динамически программируемых логических модулей (УДПЛМ), поставлена в общем виде, то сеть рассмотрены вопросы построения УДПЛМ в расчете на различные особенности требуемых логических преобразований.

В параграфе 2.1 дано краткое введение в поля Галуа, приведены основные свойства и базовая теорема разложения Менгера, на основе которой строятся переключательные функции:

ТЕОРЕМА 1(разложения Менгера). Любую переключательную функцию f{X) можно представить, причем единственным образом, в виде:

¡(Х)=т+2^С{Х\ (3) i= i

2m-l

Gi = Е aj7Í(/(°) - f})< (4) j=i

где fj = f(aj), ocj = qj - j-тая степень a, a - примитивный корень порождающего поле Галуа GF(2m) неприводимого многочлена степени т.

В параграфе 2.2 приводится методика расчета переключательных функций, представленных элементами поля Галуа GF(2m). Любой элемент X поля Галуа GF(2m) представляется в общем виде через базисные элементы поля:

X =a0a° + --- + am_1am_1. (5) Любое двоичное число (a0,ai,... ,am_i) длины тп интерпретируется как элемент поля Галуа, когда биты a¡ рассматриваются как одноименные коэффициенты из (5). Из (5) с помощью операции умножения полиномов легко получаются все X' для (3) в виде полинома от базисных элементов поля. Подсчитав для конкретной переключательной функции коэффициенты G, по формуле (4) и подставив эти значения вместе со степенями X в полиномиальном ввде в (3), после приведения подобных

мы можем получить систему полипомов Жегалкина. Каждый полином представляет собой коэффициент при базисном элементе а'. Таким образом получены алгебраические выражения, с помощью которых реализуется необходимая логическая схема, заданная таблицей входов-выходов. Рассмотренный алгоритм построен из расчета , что настроечные коэффициенты Gi будут как бы "зашиты " в схеме, за счет чего чего общий вид полиномов упростится, но при этом теряется возможность настройки схемы на разные функции. Модули, строящиеся по данному алгоритму, могут быть полезны, например, если необходимо быстрое выполнение группы часто используемых операций.

В параграфе 2.3 описывается способ построения полинома для УДПЛМ, где наряду с переменной X коэффициенты Gi также являются входными для модуля. Пугем представления G, в общем виде через базис: Gi = bioa° + ■ ■ ■ 4- и

подстановку вместе со всеми выражениями для X' в (3) получаются искомые алгебраические выражения. Для настройки УДПЛМ на конкретную функцию достаточно подсчитать значения всех Gi для этой функции по формуле (4) и занести их в регистры хранения. УДПЛМ, входными переменными и значениями которого являются двоичные числа разрядности т, в диссертации названы УДПЛМ на т входов и m выходов. В параграфе изложен способ получения настроечных коэффициентов в самой УДПЛМ, используемой как систолический вычислитель, приведены способы упрощения вычислений в зависимости от требований к режимам рабогы УДПЛМ, описаны систолические режимы работы УДПЛМ.

В параграфе 2.4 предложен метод построения то - входового модуля с помощью УДПЛМ меньшего числа входов. С ростом т сложность выражения для УДПЛМ возрастает, поэтому целесообразно получать значения любой переключательной функции на т входов и т выходов через УДПЛМ, расчитанные на меньшее число входов-выходов, то есть работающие в полях Галуа меньших порядков. Данная идея реализуется следующим образом. Для любой функции на т входов и т выходов область ее определения X - это множество всех двоичных чисел длины т. Пусть У - область значений F (двоичные числа длины не более то). Считая что входы (выходы) функции расположены слева направо, для удобства 1Щ левых входов (выходов) функции назовем младшими, остальные т2 = т — То] входов (выходов) - старшими (у пас т > тпх > тп2). Область определения X разбивается на 2"'2 классов Ki : элемент х из X принадлежит А',, если его старшие разряды представляют собой число i в двоичном виде. Каждый класс содержит 2'"1 элемента, они отличаются только младшими разрядами. На каждом Kt определим по паре функций F,, и Fi2 следующим образом. Любое х, принадлежащее Я,, представимо в виде (xi, Х2,..., xmi,xmi+i,... ,xm), причем (xm+1,... ,xm) постоянно для любого х из К^ Если у = F(x), то у также представим в виде (уиуъ ■ ■ ■ ,г/тп?Л>ч + ь • ■ ■ ,Ут) и, по определению, для х е К,- введем Fj,(x) = (уи..., ут1) и Fi2(x) = (ymi+i, ■ ■ ■ ,ут)-Так как для каждого Kt старшие разряды входных значений - это константа, то для любой Fi,, где i = 1,2, в качестве входов можно брать только младшие разряды, а

потому возможно реализовать ее в УДПЛМ па m¡ входов-выходов. Для каждой Fu

по (2) вычисляются коэффициенты G,tJ для i¡ = 0,...,2"" — 1 и j = 1.....2"" - 1.

Если х[ - входной элемент из А'„ у которого младшие разряды равны нулю, то значения функции F могуг бьпь получены через операции п поле GF(2'"') (отдельно младшие и старшие разряды) по формулам, аналогичным (3-4): F„(x) = ES"' х) + Б,2!! ' G',tJXK

— ¿-4=0 u4JP(<-r)'

где X = (j'i ,..., т1П1), p(i..v) равно 1, когда старшие разряды т совпадают с í в двоичном представлении, и равно нулю в противном случае. Иными словами, ¡i(i,x) - это терм из всех (х„,1 + 1,.. .,х,„2), причем тк берется с отрицанием, если на /.--той позиции числа i в двоичном представлении стоит 0. Дпя получения всех разрядов выходов требуется два УДПЛМ па m¡ вход и ш, выход. Возможен вариант с УДПЛМ па mi вход и mi выход плюс УДПЛМ на т2 вход и т-> выход. Тогда опять все G,,j подаются иа входы к первой УДПЛМ, a G,y подаются па входы ко второй УДПЛМ (но имеющей уже ш2 входов и ш2 выходов), причем для второй УДПЛМ роль старших разрядов играют младшие и наоборот. В этом случае объем памяти для хранения настроечных коэффициентов в точности равен требуемом памяти для УДПЛМ на т входов-выходов, но сами схемы дпя УДПЛМ проще ввиду меньшего числа входов.

В параграфе 2.5 описывается способ построения УДПЛМ для неполностью определенных переключательных функций. Пусть задано L значений функции (Z. <к 2"' - 1). Задача решается путем представления функции F(.Y) в виде:

л

F(X) = F(0) + £ АкХк. (С) n=i

i,

Ak = KjdF(.i) + f ("))> (7)

где коэффициенты Ад. зависят только от массива входов X. Матрица коэффициентов А'д получается путем решения матричного уравнения KY = Е. Все матрицы имеют размерность L х L. Е - единичная матрица. А" - Maipima искомых коэффициентов Ад и У:

Y =

/ X¡ Х2 А'з ... X,. \

X'f Jfj x¡ ... x'i x? x¡ xi ... xl

\ XI- XI' XI- ••• л;;/ где XI,..., X/, - входы переключательной функции, на которых она определена. Имея матрицу К из (7) легко, в том числе и в систолических системах, получить значения настроечных коэффициентов /Ц., используемых в (6). Сами вычисления в выражении (6) производятся так же, как для выражения (3). Матрицу К можно хра-

нить во внешней памяти, подсчитывая и подавая на входы УДПЛМ по мере надобности коэффициенты настройки /Ц-. В данном варианте по сути обнулены все коэффициенты при степенях X, больших Ь, поэтому выражения для этих степени X не нужны. Так как по условию Ь -С 2"' — 1, получаемые в данном варианте схемы для указанного класса задач более экономичны. Все вычисления производятся на ЭВМ, для чего было разработано соответствующее программное обеспечение.

Наконец, в параграфе 2.6 показана перспективность использования УДПЛМ, ввиду их функциональной полноты, для синтеза комбинационных схем ППЗУ. В отличие от ППЗУ, УДПЛМ являются чисто комбинационными, не содержащими дешифраторы, поэтому задержки сигналов в них сведены к минимуму. Предложено разделить ППЗУ на активную и пассивную части. Активная часть ППЗУ изменяет свои состояния в каждом такте, в то время как в пассивной части хранятся все настроечные коэффициенты, которые не меняют своих состояний во время процесса обращения к памяти. Переменная X является входом к активной части ППЗУ. Коэффициенты С, загружаются заранее в регистровый файл пассивной части ППЗУ в последовательной моде. В процессе обращения к ППЗУ значения С, направляются из файла регистров на входы комбинационной схемы вместе со значениями входных данных X.

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

В пара1рафе 3.1 описан способ построения таких переключателей на основе логических выражений с операциями И-ИЛИ. Задача построения переключателя формализована следующим образом. Из каждого источника в переключатель по одной бите за такт одновременно поступает двоичная информация, которую необходимо направить в приемники в соответствии с адресами коммутации, коды которых записываются в пхт матрице однобитовых элементов АО О К. Для варианта, когда в каждом такте работы переключателя из каждого приемника поступает более одной биты данных, предложено производить простое дублирование описываемого алгоритма. Рассмотрены два варианта кодирования адресов приемников данных: унитарный позиционный и двоичный код. Для унитарного кода в матрице АОБЯ столбец { содержит позиционный код адресов приемников, на которые необходимо передать данные из г-го источника. В соответствии с заданными выше условиями, в каждой строке матрицы содержится не более одной единицы. Пусть вектор-столбец /А', состоящий из п однобитовых элементов, содержит текущие значения данных из источников, то есть в /Лг, занесено значение, поступившее из источника номер г. Соответственно, эти данные должны быть переданы в вектор - столбец 011Т, состоящий из т однобитовых элементов, где в элемент 01!Т^ передаются данные для J-^aгo приемника. Переключатель строится на основе следующего выражения:

OUT — ADDR x IN. Здесь в умножении матрицы на вектор операцией умножения элементов матрицы и вектора является операция конъюнкции, сложения - операция дизъюнкции. Ввиду того, что логическое выражение предельно упрошено, такой переключатель имеет минимальные задержки. Однако, так как число входов в электронном устройстве для задания адресов приемников может быть достаточно велико (оно равняется п x m), то для сокращения этой величины до п x log2m необходимо использовать двоичный код при задании адресов приемников. В этом случае значением адреса приемника является порядковый номер выходного капала в обычном двоичном виде, что сокращает длину кода адреса до log2 m, матрица ADDR в унитарном коде формируется в самом переключателе посредством декодирования двоичного кода. Для данного типа переключателя были созданы соответствующие программы с использованием кремниевого компилятора ALTERA. Моделирование в среде MAX+PLUS II ALTERA показало, что даже для перепрограммируемых СБИС данные коммутируются с частотой 100 Мгц. Был промоделирован параллельный однокаскадный переключатель 8x8, при этом данные поступали побайтно в каждый канал входа и, соответственно, в каждом такте на каждом выходном канале формировался байт выходных данных. Таким образом, была достигнута пропускная способность 1.6 Гбнт/сек. Существенной особенностью предлагаемого типа переключателей является то, что для коммутации требуются только адреса приемников, и нет необходимости вводить в соответствующую СБИС адреса источников.

В параграфе 3.2 раскрыт способ построения 2" — 1 х 2П —й однокаскадных динамически настраиваемых переключателей на основе операций в поле Галуа GF(2n). Адреса приемников в данном случае интерпретируются как элементы поля Галуа GF(2"), и коммутация осуществляется на основе операций сложения или умножения в этом поле. Несмотря на то, что операция умножения в поле Галуа более трудоемка, данный тип переключателя может быть использован, если изменения направлений передачи имеют циклическую структуру. В этом случае можно резко сократить количество управляющих слов, в результате чего упрощается насгройка коммутатора.

В параграфе 3.3 описан способ построения переключателей с корректирующими свойствами. Рассматривается построение переключателя с использованием циклического кода Хэмминга, корректирующего одиночную ошибку, и БЧХ кода, корректирующего две ошибки. Общая схема построения переключателя с корректирующими свойствами такова. Адрес приемника кодируется соответствующим кодом, корректирующим ошибки. Код поступает на входы схемы совпадения, выходы которой подключены к схеме, корректирующей ошибку при передаче адреса, далее принцип построения переключателя аналогичен описанному ранее.

В параграфе 3.4 рассмотрен вопрос построения трассировщика данных мюон-ного детектора ATLAS с использованием описанного типа переключателей на основе автоматизированного получения адресов приемников с помощью параллельных счетчиков. В каждом цикле работы ускорителя в мюонной камере будет срабатывать 3-5% трубок MDT, поэтому необходимо коммутировать данные в буфера ввода -

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

1. В диссертации проведено исследование методов разработки алгоритмов для конвейерных вычислений в триггерных системах сбора и обработки данных в экспериментах физики высоких энергий. Основой для исследований является разработанный при участии автора и переданный в эксплуатацию в коллаборации ЦЕРН -ОИЯИ - ИНФН комплекс программ мюонного триггера установки ATLAS. Показана перспективность применения методов модулярной алгебры, аналитических вычислений и использования технологии программируемых СБИС для реализации системы тригтирования ATLAS.

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

3. Разработана методика синтеза параллельных конвейерных вычислителей на основе технологии программируемых СБИС для реализации триггерных алгоритмов.

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

5. Разработаны методы построения переключателей с использованием операций в полях Галуа GF(2n), показана возможность создания комбинаторных коммутаторов с корректирующими возможностями.

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

СПИСОК РАБОТ, ОПУБЛИКОВАННЫХ ПО ТЕМЕ ДИССЕРТАЦИИ

1. И.П.Александров, Р.И.Гайдамака, Н.М.Никтюк, В.П.Шириков. Расчет переключательных функций, представленных элементами поля Галуа GF(2'"). Препринт ОИЯИ Р10-84-865, Дубна, 1984г.

2. Александров И.Н.,Гайдамака Р.И.,Никитюк Н.М. Применение аналитических вычислений для расчета логических схем и спецпроцессоров. В книге "Аналитические вычисления на ЭВМ и их применение в теоретической фишке", Труды Международного совещания, Дубна: ОИЯИ,1985, с.295-300.

3. V.Kotov, I.Aleksandrov, R.Pose, Yu.Yatsunenko. Pipe-proccssing on systolic structures of homogeneous calculating systems for fast processing of track information. Communication of the J1NR EI0-93-19I, Dubna, 1993.

4. I.N.Alcksandrov, V.M.Kotov, N.M.Nikityuk Some questions of an application of Galois fields GF(2'") switching functions. Preprint of the JINR E10-93-412, Dubna, 1994.

5. Aleksandrov I.N., Kotov V.M., Nikityuk N.M., Pose R. Use of Computer Algebra for Calculation Switching Functions in Galois Field GF(2"'). Proceedings of "The Rhine Workshop on Computer Algebra",pp.216-219, Karlsruhe, Germany, March 22-24, 1994. Editor J.Calmet.

6. V.Kotov, I.Alexandrov, N.Nikityuk. Building of ROUTER for fast triggers. In: Proceedings of Real Time Data'94 conference,JINR, Dubna,Russia, June 27 - July 1, 1994, pp. 109-115.

7. V.Kotov, I.Alexandrov, Yu.Yatsunenko. The mathematical approach to the design of the 2nd level muon trigger for MDT and algorithm construction strategy. ATLAS Internal Note. MUON-NO-057,1994. 5 October 1994.

8. I.N.Alexandrov, V.M.Kotov, N.M.Nikityuk, R.Pose. Commutation information in Galois fields GF(2"'). Communication of the JINR E10-94-514, Dubna, 1994.

9. И.Н.Александров, В.M.Котов, Н.М.Никитюк. Применение переключательных функций в полях Галуа GF(2'") для синтеза универсальных динамически программируемых модулей. Автоматика и телемеханика, N-9, 1995, Москва, Наука, стр. 137-148.

10. I.N.Alexandrov, V.M.Kotov, N.M.Nikityuk and R.Pose. New type of programmed memories with algebraic structure.In:ESONE RTD'95 conference proceedings, Warsaw, Poland, September 27-29, 1995, pp.119-128.

Рукопись поступила в издательский отдел 15 декабря 1996 года.