Алгоритмы и программное обеспечение для реконструкции треков в детекторе переходного излучения и в мюонной системе эксперимента СВМ

Лебедев, Андрей Александрович

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

кандидата физико-математических наук: Лебедев, Андрей Александрович
город: Дубна
год: 2011
специальность ВАК РФ: 05.13.18

Диссертация по информатике, вычислительной технике и управлению на тему «Алгоритмы и программное обеспечение для реконструкции треков в детекторе переходного излучения и в мюонной системе эксперимента СВМ»

Автореферат диссертации по теме "Алгоритмы и программное обеспечение для реконструкции треков в детекторе переходного излучения и в мюонной системе эксперимента СВМ"

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

10-2010-135

На правах рукописи УДК 519.254; 539.1

И

ЛЕБЕДЕВ Андрей Александрович 0И4Ь

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

Специальность: 05Л3.18 — математическое моделирование, численные методы и комплексы программ

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

7 3 ЯКЗ 2011

Дубна 2010

004618884

Работа выполнена в Лаборатории информационных технологий Объединенного института ядерных исследований.

Научный руководитель: доктор физико-математических наук,

профессор

Ососков Геннадий Алексеевич, ЛИТ ОИЯИ, г. Дубна Официальные оппоненты: доктор физико-математических наук,

профессор

Никитин Владимир Алексеевич, ЛФВЭ ОИЯИ, г. Дубна кандидат физико-математических наук Прокудин Михаил Сергеевич, ИТЭФ, г. Москва

Ведущая организация: Петербургский институт ядерной физи-

ки им. Б.П. Константинова

Защита состоится /ъА- г. в ^^ часов на засе-

дании диссертационного совета Д 720.001.04 в Лаборатории информационных технологий Объединенного института ядерных исследований, г. Дубна Московской области.

С диссертацией можно ознакомиться в библиотеке ОИЯИ. Автореферат разослан «_£_» О^^ХУ/Ы^- 2ою г.

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

профессор {/(/V ~~~ Иванченко Иосиф Моисеевич

Общая характеристика работы

Актуальность работы. Эксперимент СВМ (Compressed Baryonic Matter) [1] но изучению новых состояний ядерной материи, образующихся в ядро-ядерных соударениях при энергиях пучка 8 -г 45 АГэВ, является одним из основных в программе исследований на строящемся в Дармштадте (Германия) ускорительном комплексе FAIIl (Facility for Antiproton and Ion Research). Задачи обработки экспериментальных данных в темпе их поступления являются одними из ключевых для успешной реализации эксперимента свм. К числу этих важных задач относится реконструкция траекторий заряженных частиц — треков, обычно называемой в литературе тренингом.

Для реконструкции траекторий частиц в эксперименте СВМ используется система детекторов, которая, в частности, включает: 1) кремниевый детектор STS (Silicon Tracking System), 2) детектор переходного излучения TRD (Transition Radiation Detector) и 3) мюонную систему MUCH (MUon CHamber) . В детекторах TRD и MUCH координатные плоскости чередуются со слоями вещества, предназначенного для получения переходного излучения от пролетающих через них электронов (радиаторы в детекторе TRD), или поглощения адронов (абсорберы в детекторе MUCH).

Большая множественность вторичных частиц в каждом соударении (до 1000), летящих в узком полярном угле (25°), наличие большого количества вещества в исследуемых детекторах и неоднородность магнитного поля осложняют задачу и требуют существенного развития известных и разработки новых методов и средств реконструкции треков, способных эффективно и стабильно работать в таких условиях.

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

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

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

Для реализации поставленной цели решены следующие основные задачи:

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

2. создание комплекса программ на основе разработанного алгоритма реконструкции треков и его применение в исследуемых детекторах;

3. проведение исследований по оптимизации структуры детекторов TRD и MUCH с последующей выработкой требований по их координатному разрешению;

4. разработка алгоритма быстрого онлайн (режим реального времени) трекинга с применением параллельных вычислений и его применение в рассматриваемых детекторах;

5. включение разработанных алгоритмов в программную оболочку эксперимента СВМ — CBMROOT и выполнение моделирования и тестирования алгоритмов в CBMROOT.

Научная новизна. Основные результаты работы являются новыми и заключаются в следующем:

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

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

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

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

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

6. Проведена оптимизация структуры детекторов TRD и MUCH, включая разные типы детектирующих элементов, на основе критериев эффективности и точности восстановления треков.

Достоверность и обоснованность результатов , полученных в диссертации, подтверждена моделированием методами Монте-Карло с применением широко известных моделей и программ, таких как UrQMD [2], GEANT [3] при использовании реалистичных параметров детекторов, а также при применении разработанного программного обеспечения членами коллаборации СВМ для физического анализа и методических исследований. Научная и практическая значимость.

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

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

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

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

4. На основе исследований, выполненных автором по оптимизации детекторов TRD и MUCH, сформулированы требования к их координатному разрешению.

На защиту выносятся следующие основные результаты и положения:

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

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

3. Результаты сравнительного анализа алгоритма экстраполяции треков, входящего в состав предложенной методики реконструкции треков, с известным пакетом по экстраполяции треков GEANE, используемым в программе GEANT3.

4. Результаты исследований по оптимизации структуры детекторов TRD и MUCH с последующей выработкой требований по координатному разрешению детекторов.

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

6. Включение разработанных алгоритмов в программную оболочку эксперимента СВМ и выполнение моделирования и их тестирования.

Апробация работы. Результаты исследований, изложенные в диссертации, были представлены:

• на международных конференциях:

- Advanced Computing and Analysis Techniques in Physics Research (ACAT) (Италия, 2008; Индия, 2010);

- Computing in High Energy and Nuclear Physics (CHEP) (Прага, 2009);

- Mathematical Modeling and Computational Physics (MMCP) (Дубна, 2009);

- Nuclear Electronics and Computing (NEC) (Варна, 2009);

• на 7 регулярных полугодовых отчетных сессиях сотрудничества СВМ в 2006-2010 годах;

• на 4-х ежегодных конференциях молодых ученых и специалистов ОИЯИ в 2005-2008 годах;

• на ежегодных заседаниях Немецкого Физического Общества (DPG) (Дармштадт, 2008; Вохум, 2009; Бонн, 2010);

• а также на научных семинарах в Лаборатории информационных технологий ОИЯИ и совещаниях группы СВМ в GSI.

Публикации. По материалам диссертации опубликовано 18 работ [Al, А2, A3, A4, А5, А6, А7, А8, А9, А10, All, А12, А13, А14, А15, А16, А17, А18], в том числе 2 работы из Перечня ВАК [Al, А2].

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

Структура и объем диссертации. Диссертационная работа состоит из Введения, 4 глав, Заключения, содержит 97 страниц, 38 иллюстраций и список литературы из 61 пункта.

Содержание работы

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

В первой главе дается краткое описание проекта СВМ — эксперимента с фиксированной мишенью на строящемся ускорительном комплексе FAIR.

В разделе 1.1 обсуждается физическая программа эксперимента СВМ. Одна из основных целей эксперимента СВМ — это изучение сжатой барионной материи. В экспери-

Рис. 1. Схема установки СВМ: для идентификации электронов [слева] и для идентификации мюонов [справа].

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

В разделе 1.2 дается описание установки СВМ. В настоящей концепции эксперимента разрабатываются два альтернативных варианта установки СВМ: первый — для идентификации электронов, второй — для идентификации мюонов. Экспериментальная установка СВМ содержит следующие детекторы (см. рис. 1): STS (Silicon Tracking System) I и MVD (Micro-Vertex Détecter), которые располагаются внутри магнита и будут использоваться для реконструкции траекторий заряженных частиц, вершин и импульсов; детектор черепковского излучения RICH (Ring Image CHerenkov) и детектор переходного излучения TRD (Transition Radiation Detector), составляющие систему идентификации электронов; времяпролетный детектор TOF (Time-Of-Flight), предназначенный для измерения времени пролета частицы и идентификации адронов; электромагнитный калориметр ECAL (Electromagnetic Calorimeter), используемый для идентификации электронов и фотонов. Для идентификации мюонов детектор RICH заменяется на мюонную систему MUCH (MUon CHamber). В этом случае первая станция TRD используется только для трекинга частиц (остальные станции TRD в этом варианте не используются).

В разделе. 1.3 приведено краткое описание детектора переходного излучения TRD, который служит для реконструкции траекторий заряженных частиц и идентификации вы-сокоэнергетичных электронов и позитронов (7 > 2000). В настоящий момент стандартный вариант модели детектора TRD содержит 3 станции, расположенные, соответственно, на

расстояниях 5 м, 7 м и 9 м от мишени. Отдельная станция включает 4 детектирующих слоя, каждый из которых состоит из различных материалов с общей толщиной 6 см. Детектирующие слои имеют мелкоячеистую структуру с ячейками прямоугольной формы. Ориентация ячеек меняется на 90 градусов от слоя к слою. Пространственное разрешение детектора составляет 0.03-0.05 см поперек ячейки и 0.27-3.3 см вдоль ячейки [1].

В разделе 1-4 рассматривается мюонпая система MUCH. Одна нз основных задач мюонной системы — подавление адронного фона и регистрация частиц, прошедших весь детектор. Мюсшкая система состоит из: шести адронных фильтров (абсорберов) различной толщины, сделанных из железа, и трех координатных детекторов после каждого абсорбера [4]. Общая толщина адронного фильтра для измерений мгоонов от распадов легких векторных мезонов (р, ы, ф) составляет 125 см железа, для мюонов от распада чармо-ния — 225 см железа. В стандартной модели мюонной системы использовались детекторы пиксельного типа — GEM (Gas Electron Multiplier). При моделировании используется сегментация детектирующих станций с учетом 5% загруженности детекторов. Минимальный размер ячейки 4x4 мм2, что соответствует разрешению по каждой координате 1.1 мм, . максимальный размер — 32 х 16 мм2 (координатное разрешение 9.2 мм на 4.6 мм). Для последних станций мюонной системы, где плотность частиц значительно ниже, рассматривается возможность применения детекторов, построенных по технологии «строу трубок» [5|, подобных тем, которые используются в эксперименте ATLAS и которые создаются в ЛВЭ

оияи.

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

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

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

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

Третья глава дает описание разработанных алгоритмов реконструкции треков в детекторах TRD и MUCH эксперимента СВМ.

Реконструкция треков в TRD и MUCH основана на применении методов слежения по треку и фильтра Калмана и использует найденные в детекторе STS треки в качестве начальных приближений для организации процедуры слежения. Основными логическими компонентами алгоритма реконструкции являются процедуры оценки параметров, экстраполяции и поиска треков. Для реконструкции треков в STS детекторе используется процедура, основанная на применении клеточных автоматов [8].

В разделе 3.1 рассмотрены проблемы, связанные с применением фильтра Калмана для оценки параметров траекторий частиц в детекторах TRD и MUCH. Использовать фильтр Калмана для оценки параметров трека было предложено в работе [7], в которой трек представляется в виде динамической системы. Это возможно сделать, определив вектор состояния динамической системы некоторым вектором х. В экспериментах с фиксированной мишенью (см. например [9, 10]) вектор х определяется в виде функции координаты z: х = х (z) и состоит из 5 параметров, однозначно определяющих трек в каждой точке:

z(z) = ( x,y,tx,tv,q/p ) ,

где х и у - координаты положения трека, tx = tv = q - заряд, равный ±1 и р - импульс частицы. Вектору х соответствует ковариационная матрица размером 5x5 С = cov {х}. Для оценки параметров трека используется вектор состояния на дискретном

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

Хк = + й!к-1-

Оценки предсказанного вектора состояния, а?*, и его ковариационной матрицы, Сц, вычисляются в алгоритме экстраполяции треков (см. следующий раздел). В случай экстраполяции трека в магнитном поле система будет нелинейной, следовательно, необходимо использовать расширенный фильтр Калмана [7], в котором потребуются линеаризация и вычисления якобиана.

В момент времени к производится измерение тк состояния системы хк в соответствии с моделью измерения:

тк = Нкхк + ек, (1)

где Нк — матрица, описывающая модель измерения, которая отображает пространство векторов состояния системы в пространство векторов результатов измерений; ек — вектор ошибок измерений, элементы которого распределены по нормальному закону с математическим ожиданием равным 0. Вектору ед. соответствует матрица ковариаций Ук: Ук = соу{ек}-

Итерация в фильтре Калмана выполняется в два этапа: Предсказание и Учет измерений. Этап предсказания использует вычисленное на предыдущем шаге состояние системы для получения оценки состояния системы на текущем шаге. Этап учета измерения используется для корректировки оценки состояния системы, что делает её в результате более точной. Операции предсказания и учета измерения повторяются до тех пор, пока в трек не будут добавлены все его отсчеты. Последний вектор состояния дает наилучшую оценку параметров трека, которая собрала в себе информацию о всех измерениях. Чередование операций предсказания и учета измерений графически показано на рис. 2. Показано отклонение частицы в слое материала между детектором к - 1 и к. Фильтр Калмана учитывает этот эффект, увеличивая предсказанную ошибку для вектора состояния на (¡к-1- Затем вектор состояния «притягивается» к истинной траектории, учитывая информацию к-го измерения, что уменьшает ошибки параметров трека.

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

к-1 к к+1

Рис. 2. Схема работы фильтра Калмана. Сплошной линией показана истинная траектория частицы. Пунктирной - экстраполяция параметров трека и ошибок параметров трека.

многократное рассеяние и неоднородность магнитного поля. Поправки для импульса, учитывающие прохождение частицы через материал детектора, вычисляются по ожидаемым средним потерям энергии за счет ионизации (формула Бете-Блоха), тормозного излучения (формула Бете-Гайтлера) и рождения элсктронно-позитронных пар. Влияние многократного рассеяния на матрицу ковариаций учитывается путем добавления ошибок, связанных с неопределенностью отклонения частицы в материале в какую-либо сторону во время экстраполяции трека. Для этого используется формула Хайланда (гауссово приближение), по которой вычисляется угол рассеяния. Геометрическая экстраполяция делается в соответствии с уравнением движения частицы. Для частицы, находящейся в области магнитного поля, решается уравнение движения заряженной частицы в магнитном поле методом Рунге-Кутта четвертого порядка. Транспортная матрица вычисляется интегрированием производных вдоль так называемой «нулевой траектории» также с использованием метода Рунге-Кутта четвертого порядка. При отсутствии магнитного поля для экстраполяции и вычисления транспортной матрицы используется прямая линия. При экстраполяции трека отрезок траектории делится на заданное количество шагов. Разделение на шаги необходимо для работы алгоритма поиска пересечений с элементами детектора при наличии магнитного поля и алгоритма учета эффектов от прохождения частицы через вещество детектора. Графически работа алгоритма экстраполяции треков показана на рис. 3.

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

Для повышения достоверности присоединения отсчетов к треку вычисляется до-

Рис. 3. Схема алгоритма экстраполяции треков. Пунктирными линиями показан поиск точек пересечения траектории частицы с элементами детектора (навигация в геометрии); сплошными линиями показана экстраполяция трека.

пуетимая область поиска. В случае алгоритмов, основанных на фильтре Калмана, допустимая область поиска на к-ой координатной плоскости может быть вычислена как ук = ТкВ^т^ < й, где Гк и Як — вектор невязок и его матрица ковариаций и (I — выбранная вероятность отбросить хороший отсчет.

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

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

Распознанные таким образом треки образуют массив треков-кандидатов, среди которых присутствуют и ложные треки, состоящие из схожего набора отсчетов, и из набора отсчетов от разных частиц. Поэтому после процедуры распознавания идет этап глобального отбора треков, на котором отбрасываются неверно найденные треки-кандидаты, а хорошие треки сохраняются с высокой эффективностью. Алгоритм отбора работает в два этапа. Сначала треки сортируются по признаку качества, который определяется на основе их длины и вычисленному в процедуре оценки параметров трека с помощью фильтра Калмана значению х2 = ь'к, где п — количество отсчетов в треке. Затем, начиная с

треков с наилучшим качеством, проверяются все его отсчеты и подсчитывается количество общих отсчетов, принадлежащих также другим трекам. Если это количество превышает 15% от общего числа отсчетов трека, то трек отбрасывается.

В разделе 3-4 приводится анализ результатов работы алгоритмов оценки параметров и поиска треков, а также результаты исследований по оптимизации детекторов TRD и MUCH.

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

1. Невязки, показывающие разность между смоделированным и вычисленным в алгоритме значением параметра трека:

residualx = х^с ~ хтес,

где хмс ~ значение параметра трека, смоделированное по методу Монте-Карло, и хгес — вычисленное значение параметра трека;

2. Нормированные невязки или пуллы (от англ. pull), показывающие правильность оценки ошибок параметров трека:

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

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

Тестовая выборка состояла из смоделированных событий, каждое из которых содержало по 10 «сигнальных» частиц (т.е. электронов и позитронов в случае TRD или мюонов в случае MUCH), рожденных в области мишени, со следующими начальными параметрами.

Для мюонов: импульс р = (2.5 - 25) ГэВ/с, полярный угол в = (2.5 - 25)" и азимутальный угол ф = (0 - 360)°. Для электронов: поперечный импульс рт = (0 - 3) ГэВ/с, полярный угол в = (2.5 — 25)° и азимутальный угол ф = (0 - 360)°.

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

Было проведено исследование по сравнению разработанного алгоритма экстраполяции треков с известным пакетом по экстраполяции треков GEANE [11]. Этот пакет используется в программе GEANT3 [3] и включает детальный учет геометрии детекторов, вещества, магнитного поля и т.д. Сравнение показало хорошее соответствие результатов разработанного алгоритма и подхода, использованного в GEANE. При этом скорость работы предложенного алгоритма оказалась в 5 раз выше. Кроме того, сложность и структура алгоритмов GEANE не позволяла их дальнейшую оптимизацию и распараллеливание, необходимые для целей эксперимента СВМ.

Алгоритм Невязки

х [см] у [см] tx ty q/p ](ГэВ/с)-1]

Экстраполяция 3.1 3.1 0.0179 0.0178 0.0035

Оценка параметров 0.53 0.33 0.0091 0.0084 0.0035

Алгоритм Пуллы

X у ¿х ty q/p

Экстраполяция 1.14 1.13 1.14 1.13 1.0

Оценка параметров 0.99 1.09 1.1 1.15 1.0

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

Результаты работы алгоритмов тренинга для TRD и MUCH. Эффективность работы алгоритма реконструкции треков определяется как отношение правильно восстановленных треков к числу треков, зарегистрированных в исследуемых детекторах. Кроме

Алгоритм Невязки

х [см] у [см] ix ty q/p [(ГэВ/с)-']

Экстраполяция 0.93 0.88 0.0024 0.0023 0.0816

Оценка параметров 0.05 0.05 0.0013 0.0013 0.084

Алгоритм Пуллы

x у tx Ч q/p

Экстраполяция 1.05 1.23 1.22 1.28 0.81

Оценка параметров 1.08 1.11 1.17 1.18 0.79

Таблица 2. Значения дисперсий для распределений невязок и пуллов подогнанных функцией нормального распределения Гаусса для детектора переходного излучения TRD.

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

Моделирование событий для тестирования алгоритмов трекинга производилось с использованием генератора частиц UrQMD [2]. Моделировались центральные Аи+Аи столкновения при начальной энергии 25 ЛГэВ. Эти события использовались для оценки фона, в который добавлялись по 10 «сигнальных» частицы, аналогичных тем, что описаны в предыдущем разделе.

Графики зависимости эффективности работы алгоритмов трекинга от импульса частицы представлены на рис. 4 для мюонной системы для трех разработанных алгоритмов трекинга: ближайший сосед (пп), ветвление (branching) и весовой (weight). Слева показаны графики эффективности поиска всех треков. Справа — графики эффективности поиска мюонов. Как и ожидалось, алгоритм ветвления показал наилучшую эффективность (91.4% для всех треков и 94% для мюонов). Алгоритм ближайшего соседа лишь незначительно уступает по эффективности алгоритму ветвления (91.2% и 93.8% соответственно). Весовой алгоритм оказался наименее эффективным (85.9% и 89.9% соответственно).

1 0.8 0.6 0.4 0.2

°0

Efficiency

—— branch (0.914) ........ nn (0.912)

■ weight (0.859)

10 15 20 25 Momentum [GeV/c]

1 0.8 0.6 0.4 0.2

Efficiency —•— branch (0.94)

nn (0.938) ■■■■■» weight (0.899)

5 10 15 20 25 Momentum [GeV/c]

Рис. 4. Графики зависимости эффективности распознавания треков в мюониой системе от импульса для трех алгоритмов трекинга: ближайший сосед (nn), ветвление (branching) и весовой (weight). Слева: эффективность распознавания всех треков. Справа: эффективность распознавания мюонов.

Графики зависимости эффективности работы алгоритмов трекинга от импульса частицы представлены на рис. 5 для детектора TRD. Результаты представлены для двух алгоритмов трекинга: ближайший сосед (nn) и ветвление (branch). Слева показаны графики эффективности поиска всех треков. Справа — графики эффективности поиска электронов. Как и в случае мюонного детектора, алгоритм ветвления показал наилучшую эффективность (91.3% для всех треков и 90.9% для электронов). Алгоритм ближайшего соседа незначительно уступает по эффективности алгоритму ветвления (87.8% для всех треков и 89.8% для электронов). Эффективность поиска электронов незначительно уступает эффективности поиска, например, пионов или мюонов. Это связано прежде всего с тем, что основная потеря энергии у электронов идет за счет тормозного излучения, имеющего длинный «хвост» распределения.

Результаты исследований по оптимизации детекторов MUCH. Было предложено и проведено систематическое исследование следующих геометрий мюонной системы: 1)MUCH1 — стандартная мюонная система с 18 GEM станциями; 2)MUCH2 — мюонная система с 13 GEM станциями; 3)MUCH3 — мюонная система с О GEM станциями и 9 станциями, построенными по технологии «строу трубок»; 4)MUCH4 — то же самое, что и MUCH2, но GEM станции после последнего абсорбера заменены на первую станцию TRD; 5)MUCH5 — то же самое, что и ЮТСНЗ, но «строу» станции после последнего абсорбера заменены на первую

0

1 0.8

0.6 0.4 0.2

°0

Efficiency all — branch (0.913) nn (0.878)

10 15

Momentum [GeV/c]

& с

e

UJ

НЙзШЙ

<bL

Efficiency electrons —•— branch (0.909) ... .... nn (0.898)

5 10 15

Momentum [GeV/c]

Рис. 5. Графики зависимости эффективности распознавания треков в TRD от импульса для двух алгоритмов трекинга: ближайший сосед (nn) и ветвление (branching). Слева: эффективность распознавания всех треков. Справа: эффективность распознавания электронов.

Алгоритм Геометрия мюонной системы

MUCH1 MUCH2 MUCH3 MUCH4 MUCH5

Ближайший сосед 93.8 94.4 93.8 92.8 92.8

Ветвление 94.0 94.7 94.1 94.9 94.9

Таблица 3. Эффективность распознавания мюонных треков для различных геометрий мюонной системы в %.

станцию TRD. В таблице 3 приведены эффективности распознавания треков в исследуемых MUCH геометриях для двух алгоритмов трекинга (ближайший сосед и ветвление). Алгоритм показал примерно одинаковую эффективность распознавания треков во всех исследуемых вариантах геометрий MUCH детекторов. Небольшая разница в эффективности вызвана также различным аксептапсом детектора в разных вариантах.

Таким образом, показана возможность использования детекторов типа «строу» для последних станции мюонной системы. «Строу трубки» являются более дешевой альтернативой по сравнению с GEM детекторами. Более того, использование первой TRD станции после последнего абсорбера позволяет уменьшить затраты на строительство мюонной системы.

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

X 1г

о к

s °4 Ii °-8Е

ш 0.7г 0.б|

°-5i 0.4F-

о.зР-

о.г|

0.4

0е-

Efficiency — all

" reference

^ftesolution1fmum]

>. 1 с 0.9

ш

о 0.8 § 0.7 0.6 0.5 0.4 0.3 0.2 0.1 0

t........

Г - .....i v............-

Efficiency \"

(0-10)"

....... (10-20)°

. (20-30)"

Г i i I M;;M I i i ! i ii i ;

10

Resolution fmum]

Рис. 6. Графики зависимости эффективности распознавания треков от координатного разрешения детектора. Справа: эффективность поиска всех треков (all) и «жестких» треков (reference). Слева: эффективность поиска «жестких» треков для различных полярных углов.

те х было фиксировано и составляло 300 цм. По координате у оно менялось от 100 ¿ш до 30 см. Использовался трекинг, основанный на алгоритме ближайшего соседа. Эффективность распознавания треков представлена на рис. С. Эффективность остается приемлемой вплоть до координатного разрешения в несколько сантиметров. Для больших полярных углов, где плотность треков меньше, разрешение детектора может составлять до 6-7 см.

Четвертая глава посвящена применению параллельных вычислений в реконструкции треков.

Раздел посвящен временной оптимизации и адаптации алгоритмов к их векторизации и распараллеливанию с целью радикального ускорения вычислений, необходимого для реализации онлайн режима обработки данных. В работе [12] предложен алгоритм векторизованного фильтра Калмана, который был расширен и применен для детекторов TRD и MUCH.

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

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

Первоначальная скалярная версия алгоритма экстраполяции треков использует алгоритм навигации в геометрии детектора, основанный на пакете TGeo из ROOT [13]. Это точный метод для навигации в геометрии детектора, однако, не очень эффективный с точки зрения скорости. Во-первых, он использует детальную модельную геометрию детектора, состоящую из 800000 элементов. Во-вторых, алгоритм навигации достаточно общий, рассчитан на любой возможный детектор и не оптимизирован для установки СВМ. Помимо этого, его невозможно использовать в векторных вычислениях. Поэтому пришлось разработать упрощенную геометрию детектора и оптимизировать алгоритм навигации. Упрощенная геометрия детектора создается путем преобразования детальной модельной геометрии в более простую, состоящую только из плоскостей, перпендикулярных к направлению пучка. Навигация в такой геометрии выполняется существенно быстрее.

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

В разделе 4-% делается обзор используемых методов и технологий для параллельных вычислений. Это SIMD (Single Instruction Multiple Data), реализованный, например, посредством SSE (Streaming SIMD Extensions) (14], и многопоточность, реализованная с использованием библиотеки ТВВ (Threading Building Blocks) [15].

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

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

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

Ускорение в 92 раза для алгоритма оценки параметров треков было достигнуто за счет существенной оптимизации алгоритма (см. раздел 4.1). Векторизация алгоритмов и данных привела к 3-х кратному ускорению. Запуск векторизованной процедуры оценки параметров треков параллельно в нескольких потоках дало выигрыш в 8.8 раз для машины с 8-ю ядрами. В итоге было достигнуто ускорение в 2400 раз (с 1200 мкс/трек до 0.5 мкс/трек).

Моделирование событий для тестирования параллельного алгоритма трекинга проводилось с теми же параметрами, что и для тестирования первоначальной скалярной версии трекинга. Сравнение первоначальной скалярной версии алгоритма трекинга и параллельной версии показало, что при одинаковой эффективности поиска треков, параллельный алгоритм гораздо быстрее (см. таблицу 4). Ускорение в 101 раз достигнуто за счет оптимизации алгоритма и использования ускоренных процедур фильтра Калмана. Векторизация и многопоточность дают меньшее ускорение, чем для алгоритма оценки параметров. Это связано с тем, что некоторые части алгоритма трекинга не полностью векторизованы и параллельны. В итоге, параллельный алгоритм трекинга работает в 487 раз быстрее, чем первоначальный скалярный последовательный алгоритм (с 730 мс/событие до

Оценка параметров Поиск

Время [мкс/трек] Ускорение Время [мс/событие] Ускорение

Начальная 1200 - 730 -

Оптимизация 13 92 7.2 101

Векторизация 4.4 3 4.9 1.5

Многопоточность 0.5 8.8 1.5 3.3

Финальная 0.5 2400 1.5 487

Таблица 4. Времена вычислений и коэффициенты ускорения для алгоритмов оценки параметров

и поиска треков в мюонном детекторе. 1.5 мс/событие).

В Заключении сформулированы основные выводы диссертационной работы:

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

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

3. Проведены исследования по оптимизации структуры детекторов TRD и MUCH. В результате исследований показана возможность использования для мюонной системы более дешевых детекторов на основе технологии «строу трубок» и первой станции TRD. Сформулированы требования по координатному разрешению TRD детектора.

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

Список публикаций

AI. Lebedev А., Höhne С., Kisel I., Ososkov G. Fast parallel tracking algorithm for the muon detector of the CBM experiment at FAIR // Письма в ЭЧАЯ. 2010. Т. 7, № 4(164). С. 473-482.

А2. Lebedev А., Höhne С., Kisel I., Ososkov G. Fast Global Tracking for the CBM Experiment at FAIR // Вестник РУДН. Серия Математика. Информатика. Физика. 2010. Т. 2, № 2. С. 59-63.

A3. Lebedev A., Lebedev S., Ososkov G. Pattern recognition methods for data handling of the CBM experiment // Сообщ. ОИЯИ 10,11-2010-22. 2010. С. 191-201.

A4. Лебедев А., Ососков Г. Реконструкция траекторий частиц в детекторах TRD и MUCH эксперимента СВМ // Сообщ. ОИЯИ Р10-2010-3. 2010. Т. 2, № 2. С. 58-62.

А5. Lebedev A., Ososkov G. Track reconstruction algorithms for the CBM experiment at FAIR // J. Phys.: Conf. Ser. Vol. 219. P. 032048.

A6. Senger P., Galatyuk Т., Kiseleva A. et al. The compressed baryonic matter experiment at FAIR // J. Phys. G: Nucl. Part. Phys. 2009. Vol. 36. P. 064037.

A7. Lebedev A., Höhne С., Kisel I. et al. Track Reconstruction and Muon Identification in the Muon Detector of the CBM Experiment // PoS(ACAT08) 068.

A8. Lebedev A., Ososkov G. LIT Track Propagation for CBM // CBM note QCD_CBM_SOFT-note-2008-002. 2008.

A9. Иванов В., Лебедев А., Лебедев С., Ососков Г. К вопросу об оптимизации геометрии детектора переходного излучения для эксперимента СВМ // Сообщ. ОИЯИ Р10-2008-152. 2008.

А10. Lebedev A., Ososkov G. Event Reconstruction in the CBM TRD // CBM note QCD_CBM_SOFT-note-2008-001. 2008.

All. Lebedev A., Ososkov G. Track reconstruction in the CBM TRD // Сообщ. ОИЯИ E10-2008-3. 2008.

А12. Лебедев А., Лебедев С., Ососков Г. Реконструкция событий в эксперименте СВМ // Сборник трудов XII конференции молодых ученых и специалистов. 2008.

А13. Лебедев А., Ососков Г. Реконструкция событий в детекторах STS и TRD эксперимента СВМ // Сборник трудов XI конференции молодых ученых и специалистов. 2007.

А14. Lebedev A., Baginyan S., Ososkov G. Kalman filter application for the CBM TRD track recognition // Сборник трудов X конференции молодых ученых и специалистов. 2006.

А15. Lebedev A., Hohne С., Kisel I., Ososkov G. Fast parallel tracking algorithm for the muon detector of the CBM experiment // GSI Scientific Report 2009. 2010. P. 59.

A16. Lebedev A., Hohne C., Kisel I., Ososkov G. Status of the global track reconstruction algorithm for the CBM experiment // GSI Scientific Report 2009. 2010. P. 53.

A17. Lebedev A.j Hohne C., Kisel I., Ososkov G. Track reconstruction in the MUCH and TRD detectors of CBM // GSI Scientific Report 2008. 2009. P. 33.

A18. Lebedev A., Ososkov G. Track reconstruction in the TRD and MuCh detectors // GSI Scientific Report 2007. 2008. P. 25.

Цитированная литература

1. Compressed Baryonic Matter Experiment — Technical Status Report. 2005. URL: https: //www.gsi.de/documents/D0C-2005-Feb-447.html.

2. Bass S. et al. // Prog. Part. Nucl. Phys. 1998. Vol. 41. Pp. 255-370.

3. GEANT - Detector Description and Simulation Tool. 1993.

4. Киселева А. Ядерно-физическое обоснование проведения измерений димюонного канала распада векторных мезонов в СВМ эксперименте: Ph.D. thesis / ПИЯФ. 2009.

5. Peshekhonov V. et al. Segmented straw tubes for CBM-MuCH // CBM Progress Report 2008. 2008. P. 35.

6. Kalman R. A New Approach to Linear Filtering and Prediction Problems // Transactions of the ASME - Journal of Basic Engineering. 1960. Vol. 82, no. Series D. Pp. 35-45.

7. Fruhwirth R. Application of Kalman filtering to track and vertex fitting // Nucl. Instrum. Meth. 1987. Vol. A262. Pp. 444-450.

8. Kisel I. Event reconstruction in the CBM experiment // Nucl. Instrum. Meth. 2006. Vol. A56G. Pp. 85-88.

9. Mankel R. Application of the Kalman filter technique in the HERA-B track reconstruction. 1995.

10. van Tilburg J. Track simulation and reconstruction in LHCb: Ph.D. thesis / Uni Vrije Amsterdam. 2005.

11. Innocente V., Maire M., Nagy E. GEANE: Average Tracking and Error Propagation Package. 1991.

12. Gorbunov S., Kebschull U., Kisel I. et al. Fast SIMDized Kalman filter based track fit // Сотр. Phys. Comm. 2008. Vol. 178. Pp. 374-383.

13. ROOT - An Object-Oriented Data Analysis Framework, User's Guide. 2010.

14. Intel 64 and IA-32 Architectures Software Developer's Manual. Volume 1: Basic Architecture. 2009.

15. Threading Building Blocks. URL: http://www.threadingbuildingblocks.org.

Получено I декабря 2010 г.

Отпечатано методом прямого репродуцирования с оригинала, предоставленного автором.

Подписано в печать 01.12.2010. Формат 60 х 90/16. Бумага офсетная. Печать офсетная. Усл. печ. л. 1,62. Уч.-изд. л. 1,73. Тираж 100 экз. Заказ № 57175.

Издательский отдел Объединенного института ядерных исследований 141980, г. Дубна, Московская обл., ул. Жолио-Кюри, 6. E-mail: publish@jinr.ru www.jinr.ru/publish/

Оглавление автор диссертации — кандидата физико-математических наук Лебедев, Андрей Александрович

Введение

Глава 1. Эксперимент СВМ.

1.1. Физическая программа эксперимента.

1.2. Установка СВМ.

1.3. Детектор переходного излучения TRD.

1.4. Мюонная система MUCH.

1.5. Моделирование, реконструкция и анализ событий.

Глава 2. Обзор методов реконструкции треков.

2.1. Введение.

2.2. Методы.

2.3. Выводы.

Глава 3. Реконструкция треков в эксперименте СВМ.

3.1. Введение.

3.2. Фильтр Калмана.

3.3. Экстраполяция треков

3.4. Поиск треков.

3.5. Программная реализация.

3.6. Результаты.

3.7. Выводы.

Глава 4. Применение параллельных вычислений для реконструкции треков в эксперименте СВМ.

4.1. Введение.

4.2. Адаптация алгоритмов для параллельных вычислений.

4.3. Обзор методов и технологий.

4.4. Распараллеливание алгоритма реконструкции треков.

4.5. Программная реализация.

4.6. Результаты.

4.7. Распараллеливание на уровне событий.

4.8. Выводы.

Введение 2011 год, диссертация по информатике, вычислительной технике и управлению, Лебедев, Андрей Александрович

Актуальность работы. Эксперимент СВМ (Compressed Baryonic Matter) [1] по изучению новых состояний ядерной материи, образующихся в ядро-ядерных соударениях при энергиях пучка 8 -i- 45>АГэВ, является;одним из основных в программе исследований, на строящемся в Дармштадте (Германия) ускорительном: комплексе FAIR (Facility for Antiproton and Ion Research).

Задачи, обработки экспериментальных данных в темпе их поступления являются одними из ключевых, для успешной реализации эксперимента СВМ. К числу этих важных задач относится реконструкция^ траекторий заряженных частиц — треков, обычно называемой в' литературе: трскингом.

Для реконструкции траекторий, частиц в эксперименте СВМ используется система детекторов, которая, в частности, включает: 1) кремниевый детектор STS; (Silicon Tracking System), 2) детектор переходного излучения TRD (Transition Radiation,Detector) и 3) мюонную систему MUCH (MUon CHamber) . В детекторах TRD и MUCH координатные плоскости чередуются со слоями вещества, предназначенного для получения переходного излучения от пролетающих через них электронов (радиаторы в детекторе TRD), или поглощения адронов (абсорберы в. детекторе MUCH).

Большая множественность вторичных частиц в каждом соударении (до 1000), летящих в узком полярном угле (25°), наличие большого количества вещества в исследуемых детекторах и неоднородность магнитиого поля осложняют задачу и требуют существенного развития известных и разработки новых методов и средств реконструкции треков, способных эффективно, и; стабильно работать в таких условиях.

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

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

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

Для реализации поставленной цели решены следующие основные задачи:

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

2. создание комплекса программ на основе разработанного алгоритма реконструкции треков и его применение в исследуемых детекторах;

3. проведение исследований по оптимизации структуры детекторов TRD и MUCH с последующей выработкой требований по их координатному разрешению;

4. разработка алгоритма быстрого онлайн (режим реального времени) тре-кинга с применением параллельных вычислений и его применение в рассматриваемых детекторах;

5. включение разработанных алгоритмов в программную оболочку эксперимента СВМ — CBMROOT и выполнение моделирования и тестирования алгоритмов в CBMROOT.

Научная новизна. Основные результаты работы являются новыми и заключаются в следующем:

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

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

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

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

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

6. Проведена оптимизация структуры детекторов TRD и MUCH, включая разные типы детектирующих элементов, на основе критериев эффективности и точности восстановления треков.

Достоверность и обоснованность результатов , полученных в диссертации, подтверждена моделированием методами Монте-Карло с применением широко известных моделей и программ, таких как UrQMD [2], GEANT [3] при использовании реалистичных параметров детекторов, а также при применении разработанного программного обеспечения членами коллаборации СВМ для физического анализа и методических исследований.

Научная и практическая значимость.

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

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

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