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

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

10-2011-14

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

ЛЕБЕДЕВ Семен Александрович

МАТЕМАТИЧЕСКОЕ ОБЕСПЕЧЕНИЕ ДЛЯ РЕКОНСТРУКЦИИ КОЛЕЦ ЧЕРЕНКОВСКОГО ИЗЛУЧЕНИЯ И ИДЕНТИФИКАЦИИ ЭЛЕКТРОНОВ В RICH ДЕТЕКТОРЕ ЭКСПЕРИМЕНТА СВМ

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

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

4840873

1 7 MAP 2011

Дубна 2011

4840873

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

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

Официальные оппоненты:

Ведущая организация:

Защита состоится «.

//

доктор физико-математических наук, профессор

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

А*

■кхрш,

2011 г. в

10.

часов на засе-

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

С диссертацией можно ознакомиться в библиотеке ОИЯИ. Автореферат разослан « ^ ^ » Л 2011 г.

Ученый секретарь диссертационного совета

доктор физико-математических наук, профессор {/'{Л ——

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

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

Актуальность работы. Работа посвящена одной из важных проблем экспериментальной физики высоких энергий (ФВЭ), а именно задаче реконструкции событий1, полученных в ядро-ядерных соударениях. Характерными особенностями многих современных экспериментов в физике высоких энергий являются большая множественность и плотность частиц в каждом событии (до 1000 зарегистрированных частиц в событии), а также высокая скорость поступления данных (до 107 событий/сек.). Для анализа полученных данных необходимы быстрые и эффективные алгоритмы и программы.

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

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

Одной из основных задач в эксперименте СВМ является идентификация электронов2, которая необходима для реконструкции J/ф иф' мезонов и легких векторных мезонов (р, ш, ф) при распаде по диэлектронному каналу. С одной стороны, требуется хорошая эффективность идентификации электронов, с другой стороны, необходимо хорошее подавление пионов, так как они составляют основной фон при физическом анализе. Для идентификации электронов и подавления пионов будут использованы детектор черепковского излучения RICH (Ring Imaging CHerenkov) и детектор переходного излучения

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

2 Здесь и далее предполагается идентификация электронов и позитронов.

TRD (Transition Radiation Detector).

Детекторы RICH широко применяются во многих экспериментах в физике высоких энергий как часть системы идентификации частиц (см., например, [A3, A4, А5, А6] и обзор [А7]). Принцип работы RICH детектора основан на том, что при прохождении частицы в среде, характеризуемой показателем преломления п, со скоростью v, превышающей скорость света в данной среде, испускается черепковское излучение под углом в к траектории движения частицы, при этом cos6 = 1/ßn, где ß = v/c. Угол в зависит от типа частицы и ее импульса. В RICH детекторах черенковские фотоны регистрируются напрямую фотодстектором (или фокусируются сферическим зеркалом на фотодетектор) в виде изображения колец. Скорость заряженной частицы определяется по радиусу кольца, на котором располагаются фотоны, в соответствии с конструкцией и оптической системой детектора. RICH детектор часто используется для идентификации частиц совместно с детектором для измерения импульса, так как совокупность информации о скорости и импульсе частицы позволяет определить ее массу, по которой она может быть идентифицирована. Для определения угла, под которым испускается черенковское излучение, необходимо распознать и оценить параметры колец. Поэтому реконструкция колец в событиях является важной задачей для всех RICH детекторов.

В диссертации представлены алгоритмы реконструкции событий в RICH детекторе эксперимента СВМ. К этим алгоритмам предъявляются следующие требования: 1) высокая скорость работы алгоритмов из-за необходимости обрабатывать большой поток данных, 2) высокая эффективность распознавания колец, 3) устойчивость вычислений к обработке событий с большой множественностью частиц. Проведенный анализ показал, что существующие алгоритмы не удовлетворяют таким требованиям по эффективности и/или скорости работы. Поэтому возникла необходимость развития существующих и разработки новых, более эффективных алгоритмов. Одним из способов ускорения процесса обработки являются параллельные вычисления. Современная архитектура процессоров развивается по пути увеличения количества вычислительных ядер и применения векторных вычислений, что позволяет существенно повысить эффективность работы программ при использовании параллельных алгоритмов.

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

цию RICH детектора.

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

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

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

2. разработать эффективный алгоритм идентификации электронов в RICH детекторе;

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

4. реализовать алгоритмы в программной оболочке эксперимента СВМ — CBMROOT, и выполнить их тестирование;

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

6. провести исследования по оптимизации конструкции RICH детектора и выработать требования по ее улучшению.

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

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

2. Предложен и программно реализован оригинальный критерий оценки качества найденных колец, основанный на применении искусственной нейронной сети (ИНС).

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

3. Разработан новый алгоритм идентификации электронов в RICH детекторе, основанный на применении ИНС. Алгоритм показал двукратное преимущество в подавлении пионов по сравнению с ранее известными алгоритмами.

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

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

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

1. Разработанное программное обеспечение включено в общую программную оболочку эксперимента СВМ — CBMROOT [А10], и активно используется членами кол-лаборации СВМ. Программы применялись как на стадии развития эксперимента и его физического обоснования, так и для оптимизации создаваемой экспериментальной установки. Результаты, полученные с использованием созданных алгоритмов и программ, подтвердили необходимый уровень идентификации электронов и подавления пионов.

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

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

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

4. Алгоритмы распознавания и оценки параметров колец, разработанные в диссертации, имеют самостоятельную научную ценность и могут быть использованы в других областях науки (биологии, медицине).

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

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

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

3. Разработан алгоритм идентификации электронов в RICH детекторе, основанный на применении искусственной нейронной сети. Алгоритм показал двукратное преимущество в подавлении пионов по сравнению с ранее известными алгоритмами.

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

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

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

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

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

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

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

- Advanced Computing and Analysis Techniques in Physics Research (ACAT10) (Индия, 2010);

• на семи международных совещаниях коллаборации СВМ в 2006 - 2010 годах;

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

• на двух конференциях немецкого физического общества (Дармштадт, 2008; Бонн,

2010);

• а также на научных семинарах в Лаборатории информационных технологий ОИЯИ

и на совещаниях СВМ группы в GSI (Дармштадт, Германия).

Публикации. По материалам диссертации опубликовано 25 работ [1-25], в том числе 4 работы из Перечня ВАК [1-4].

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

Структура и объем диссертации. Диссертационная работа состоит из Введения, 4 глав, Заключения, содержит 94 страницы, 41 иллюстрацию и список литературы из 64-х пунктов.

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

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

В первой главе дается краткое описание эксперимента СВМ (Compressai Baryonic Matter) — эксперимента с фиксированной мишенью на строящемся ускорительном комплексе FAIR (Facility for Antiproton and Ion Research).

В разделе 1.1 обсуждается физическая программа СВМ. Основная цель эксперимента — это изучение сжатой барионной материи в ядро-ядерных соударениях при энергиях пучка ог 8 до 45 ЛГэВ [А1, А2]. Физическая программа исследований включает изучение фазовой диаграммы квантовой хромодинамики (КХД) в области высоких барионных плотностей и умеренных температур.

В разделе 1.2 дается описание установки СВМ. Планируемая схема расположения детекторов представлена на рис. 1. Внутри дипольного магнита расположен кремниевый детектор STS (Silicon Tracking System) и вершинный детектор MVD (Micro-Vertex Detector), которые предназначены для реконструкции треков, первичных и вторичных вершин и определения импульса частиц. Детектор черепковского излучения RICH (Ring Imaging CHerenkov) служит для идентификации электронов с импульсами до 10 ГэВ/с. Детектор переходного излучения TRD (Transition Radiation Detector) предназначен для идентификации электронов с импульсами более 1.5 ГэВ/с и трекинга заряженных частиц. Детектор времени пролета TOF (Time-of-Flight) предназначен для идентификации адронов. Электромагнитный калориметр ECAL (Electromagnetic CALorimeter) служит для идентификации фотонов и электронов. Калориметр PSD (Projectile Spectator Detector) предназначен для определения центральности соударений и плоскости реакции.

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

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

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

TOF ECAL

Рис. 1. Схема расположения детекторов в эксперименте СВМ

событий и физический анализ.

Во второй главе делается обзор известных методов реконструкции колец в RICH детекторах.

В разделе 2.1 рассматриваются известные в литературе методы распознавания колец черенковского излучения. Описаны следующие методы: 1) итерационный с предсказанной позицией центра кольца, 2) отношения функций максимального правдоподобия, 3) сравнения с эталонным изображением (метод масок), 4) нечеткая кластеризация, 5) эластичная нейронная сеть, 6) преобразование Хафа. Представлен сравнительный анализ достоинств и недостатков методов для оценки возможности их применения в эксперименте СВМ. Только два из рассмотренных методов широко применяются на практике — это метод на основе преобразования Хафа, и метод отношения функций правдоподобия. Для алгоритма реконструкции колец в RICH детекторе эксперимента СВМ предъявляются высокие требованиях к скорости работы, эффективности распознавания колец и устойчивости к событиям с большой множественностью частиц. Проведенный анализ показал, что существующие алгоритмы не удовлетворяют требованиям СВМ эксперимента по эффективности и/или скорости работы, поэтому необходима разработка новых, более

эффективных и быстрых алгоритмов.

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

Разработанный алгоритм реконструкции колец является автономным, то есть в качестве входных данных используется информация только из RICH детектора. Алгоритм состоит из трех этапов. Первый этап — локальный поиск колец-кандидатов, который основан на преобразовании Хафа. Второй этап — глобальный отбор колец, основанный на определении качества колец с использованием искусственной нейронной сети. На третьем этапе найденные кольца подгоняются эллипсом.

Преобразование Хафа — стандартный метод для распознавания фигур на изображении, например, прямых линий, окружностей, эллипсов и др. Множество кривых на плоскости задано параметрическим уравнением: F(ai,a2,аз,...,а„,х,у) = 0, где F — в общем случае непрерывная, нелинейная функция, ai, аз, ... — параметры кривой, и х, у — координаты на плоскости. В преобразовании Хафа пространство измерений преобразуется в пространство параметров. Пространство параметров имеет размерность, равную числу параметров кривой. Каждая точка в этом пространстве (определенное значение ai, аг, • • ■) соответствует определенной кривой в исходном пространстве измерений. Обычно непрерывное пространство параметров переводят в дискретное. Для этого оно разбивается на ячейки, которые можно рассматривать как ячейки гистограммы, содержимое которых равно количеству кривых, соответствующих данной ячейке. Таким образом, задачей является анализ гистограммы с целью найти в ней пики (ячейки с наибольшим числом входов). Каждая такая ячейка определяет параметры кривой на исходном изображении.

Установим соответствие между пространством измерений и пространством параметров в случае окружностей. Пространство параметров имеет размерность 3, по количеству параметров окружности (a, b — центр окружности, R — ее радиус). В пространстве параметров окружность (х — а)2 + (у — Ъ)2 = R2 представлена в виде точки с координатами (a, b, R). Параметры окружности могут быть вычислены для любой тройки точек с координатами X, У. Для преобразования всех точек в пространство параметров перебираются все тройки точек (триплеты) и вычисляются параметры окружности. Затем

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

В разделе 3.1 обсуждается разработанная модификация преобразования Хафа, которая за счет локализации перебора позволяет сократить более, чем на порядок, временные затраты на его выполнение и значительно сократить использование памяти. Так как черепковские кольца имеют максимальный радиус Н'тах из-за ограничений по углу черенковского излучения, триплеты хитов3 перебираются только в локальной области (см. рис. 2). Гистограмма, центров колец строится также только в локальной области, благодаря этому она имеет небольшую размерность (15x15), что существенно снижает использование памяти и время работы алгоритма. Размер ячейки в гистограмме был получен эмпирическим путем и равен 0.5x0.5 см2, что соответствует размеру ячейки фотодетектора.

Dmax

(xO-Dmax,yO+Dmax)

(xO+Dmax.yO+Dmax)

н -1

( п №

1

Ш

•

Ш

(xO-DmaxpyO-Dmax)

(xO+DmaxpyO-Dmax)

Рис. 2. Слева: начальный поиск хитов в локальной области. Справа: схематическая гистограмма центров колец. Втах — максимальный диаметр кольца, (жО, уО) — координаты начального хита

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

3 Хит — это измерение детектора, для RICH детектора хит содержит X и У координаты на плоскости фотодетектора.

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

В разделе 3.2 описаны алгоритмы для оценки параметров колец черепковского излучения. Были реализованы алгоритмы подгонки окружностью и эллипсом. Подгонка точек окружностью используется в алгоритме поиска колец. Реализован алгоритм, известный в литературе как СОР (Chernov-Ososkov-Pratt) [All, А12]. Наличие неизбежных оптических искажений, приводящих к тому, что большинство колец приобретают форму эллипса, потребовало также разработки алгоритмов для выявления и компенсации таких искажений. Было предложено использовать параметризацию колец не окружностью, а эллипсом. Реализовано два алгоритма подгонки эллипсом. В первом алгоритме минимизация выполняется с помощью программы MINUIT [А13]. Второй алгоритм основан на методе Таубина [А14, А15]. Результаты сравнения алгоритмов представлены в [4].

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

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

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

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

Кольца сортируются по критерию качества: самые хорошие попадают в начало массива, а самые плохие в конец. Затем, начиная с кольца с наилучшим качеством, проверяется какое количество общих хитов оно имеет с уже отобранными кольцами. Если количество совпадающих хитов не более 25%, то такое кольцо считается отобранным, в противном случае — отбрасывается. Таким образом, удаляются кольца-кандидаты с худшим качеством, которые имеют большое количество общих хитов с кольцом более высокого качества.

В разделе 3.4 описаны методы идентификации электронов в детекторе RICH. Было реализовано 3 алгоритма: 1) идентификация электронов с помощью порогового метода при подгонке окружностью, 2) идентификация электронов с помощью порогового метода при подгонке эллипсом, 3) идентификация электронов с помощью ИНС.

Подробнее опишем третий метод, показавший наилучший результат. Метод основан на использовании значимых параметров на основе которых можно различить электроны и пионы. Проведенный статистический анализ позволил отобрать 9 таких параметров: большая полуось эллипса (Л), малая полуось эллипса (В), импульс частицы, значение критерия хи-квадрат \2 эллиптической подгонки, положение кольца на фотодетекторе, угол поворота эллипса на фотодетекторе и радиальный угол, расстояние от центра кольца до ближайшего к нему трека, количество хитов в найденном кольце. Для классификации электронов и пионов по значимым параметрам использовалась ИНС типа многослойный персептрон. Выходной нейрон ИНС принимал в процессе обучения значение -1 при подаче на вход параметров, соответствующих кольцам от пионов, а в случае электронов выходной сигнал принимал значение +1. Порог на выходное значение ИНС выбирался исходя из требуемого уровня эффективности идентификации электронов.

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

уменьшена в 2 раза (с 22.8 м2 до 11.8 м2), площадь фотодетекторов в 3.5 раза (с 200000 каналов до 55000 каналов) [16].

В разделе 3.6 представлены результаты работы алгоритмов. Эффективность алгоритма определялась с использованием Монте-Карло информации. При вычислении эффективности определялась степень соответствия найденных и смоделированных колец. В качестве правильно найденных колец определяются те кольца, у которых более 60% хитов совпадает с Монте-Карло кольцом, в противном случае кольцо определяется ложным. Эффективность работы алгоритма определялась по трем критериям:

• Эффективность реконструкции колец: е// — NT,.C/Nacc, где NTtc количество правильно найденных колец, Nacc — количество колец в аксептансе RICH детектора (с количеством хитов более 4).

• Количество ложных колец на событие.

• Количество клонов на событие (т.е. колец, найденных более одного раза).

Для представленных результатов моделировались центральные Au-Au UrQMD |А8] соударения при энергии пучка 25 ЛГэВ. Эти события использовались для оценки фона. В каждое такое событие добавлялись 10 сигнальных электронов. Среднее количество колец в событии равно 80.

Результаты работы алгоритма для двух вариантов RICH детектора представлены в таблице 1. Эффективность реконструкции колец от сигнальных электронов для большого RICH (начальная версия детектора) равна 95%, количество ложных колец на событие равно 1.9 на событие, количество клонов — 0.3 на событие. Эффективность реконструкции колец для компактного RICH (оптимизированная версия детектора) равна 93%, количество ложных колец на событие равно 2.7, количество клонов — 0.9 на событие. График зависимости эффективности от импульса для компактного RICH показана на рис. 3 слева.

Сравнение результатов работы трех алгоритмов идентификации электронов в детекторе RICH представлено в таблице 2. Эффективность алгоритмов определялась по значению ошибок первого (а) и второго ()3) рода. В эксперименте СВМ принято использовать уровень подавления пионов, который вычисляется как iraupp. = Nr/NmiSn = 100//?, где N„ — это количество пионов, iVm,sjr — количество пионов идентифицированных алго-

Таблица 1. Результаты работы алгоритма реконструкции колец для двух вариантов RICH детектора _

Большой RICH Компактный RICH

Эффективность поиска, % 95 93

Кол-во ложных колец/событие 1.9 2.7

Кол-во клонов колец/событие 0.3 0.9

«0.8

0.6

0.4

0.2

+ : + *-+++ +Ч-++ "-t

100 90 80 70 60 50 40 30 20 10

0 2 4 6 8 10 12 14 momentum, GeVíc

■ Efficiency - Fake rings -Clone rings

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

ритмом как электрон. Уровень подавление пионов вычисляется исходя из 93% эффективности идентификации электронов (а = 7%). И таблицы видно, что алгоритм на основе ИНС показывает двукратное преимущество в подавлении пионов по сравнению с другими методами.

Был проведен большой объем методических исследований разработанных алгоритмов. Данные исследования необходимы для оценки устойчивости алгоритма к различным экспериментальным факторам и для определения характеристик детектора RICH и его оптимальной конструкции.

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

Таблица 2. Подавление пионов в RICH детекторе для трех различных алгоритмов

ИНС метод Пороговый метод, окружность Пороговый метод, эллипс

Подавление пионов (р < 6 ГэВ/с) 500 200 250

Подавление пионов (р > 6 ГэВ/с) 260 130 150

реконструкции остается выше 70%, при этом количество ложных колец не превышает 5%.

' .С- vO. . Ы-- } Л1?. : .'С* *

' /.к; г.! 4... г v* %

Рис. 4. Пример события со 150 кольцами

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

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

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

В раздел 4.1 рассматривается оптимизация и адаптация алгоритмов для их последу-

ющей векторизации и распараллеливания. Во-первых, была оптимизирована процедура поиска хитов, находящихся в заданной области фотодетектора. Эта процедура интенсивно используется при локальном поиске колец-кандидатов. Простой способ заключается в вычислении расстояния до каждого хита, проверки этого расстояния и отбрасывании ненужных хитов. Такая проверка всех хитов занимает много времени и, более того, большинство хитов не попадают в заданную область. Для сокращения перебора был разработан алгоритм быстрого поиска хитов. Проведенные исследования времени выполнения программы показали, что самой времязатратной частью алгоритма является процедура перебора триплетов в преобразовании Хафа. Уменьшение комбинаторики было достигнуто за счет первоначального разделения хитов на группы и выполнения перебора в каждой группе независимо. Затем результаты складывались для дальнейшего анализа. При выполнении программы на компьютере производительность алгоритма с данными, находящимися в оперативной памяти существеннее медленнее, чем при работе с данными в кэше. Была произведена оптимизация доступа к оперативной памяти и перенос данных в кэш процессора. Кроме того, были реализованы другие возможности оптимизации алгоритма, включающие в себя: точное определение локальной области поиска колец, математическую оптимизацию алгоритма, удаление хитов найденных колец, оптимизацию параметров алгоритма и др. Для увеличения производительности большинство циклов было развернуто и убраны ветвления.

В раздел 4.2 делается обзор используемых методов и технологий для параллельных вычислений. Это SIMD (Single Instruction Multiple Data — одна инструкция множество данных) — принцип компьютерных вычислений, позволяющий обеспечить параллелизм на уровне данных. Реализация сделана с помощью технологии Intel Streaming SIMD Extension (SSE) (A16], которая поддерживается всеми современными процессорами. Процессоры с технологией Intel SSE имеют набор 128 битовых регистров, каждый из которых может содержать четыре 32 битовых числа с плавающей точкой. Многопо-точность в алгоритме была реализована с использованием библиотеки Intel Threading Building Blocks (TBB) [А17]. TBB поддерживает масштабируемые параллельные вычисления. Это означает, что программа, использующая библиотеку ТВВ, будет работать на компьютере с одним процессором и на компьютере с большим количеством процессоров без необходимости вносить изменения в программу.

В разделе 4.3 описано применение векторизации в алгоритма поиска колец. Наи-

лучшим кандидатом для использования векторизации является процедура с большим количеством вычислений без ветвлений, которая может выполняться параллельно для множества данных. Все вычисления были переведены из двойной точности в одинарную. Проведенное тестирование показало, что разработанный алгоритм работает с одинарной точностью без потери эффективности. Далее данные RICH детектора были векторизованы. Это означает, что в каждый вектор хитов упаковывается 4 измерения: Xv, Yv, где Xv = (Х0,Х\,Х2,Хз), Yv — (У0,У1,У2,Уз). Вычисление параметров кольца (х, у, г) производилось с использованием SSE инструкции по трем хитам для 4 триплетов одновременно.

В разделе 4.4 описано применение многопоточности в алгоритме. Реализация включает 3 различных способа: 1) так как RICH детектор состоит из двух независимых фотодетекторов, хиты делятся на две группы по принадлежности к фотодетскторам и реконструкция колец производится параллельно в отдельном потоке для каждого фотодетектора; 2) алгоритм локального поиска позволяет выполнять поиск колец в разных областях фотодетектора независимо и параллельно в отдельных потоках; 3) перед выполнением преобразования Хафа хиты делятся на группы и преобразование выполняется в каждой группе параллельно в отдельном потоке.

Далее в разделе 4.4 приведены основные результаты но оптимизации и распараллеливанию алгоритмов реконструкции колец. Тестирование алгоритмов проводилось на компьютере с двумя процессорами Intel Core ¡7, имеющих по 4 ядра каждый с тактовой частотой 2.66 ГГц. За счет оптимизации было достигнуто ускорение алгоритма в 74 раза (с 357 мс/событие до 4.8 мс/событие). Использование векторизации и многопоточности позволило ускорить алгоритм еще в 2 раза. В итоге было достигнуто ускорение в 143 раза (с 357 мс/событие до 2.5 мс/событие) для параллельной версии в сравнении с начальной версией.

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

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

Исследование проводилось на компьютере с двумя процессорами Intel Core i7, имеющих по 4 ядра каждый с тактовой частотой 2.66 ГГц и возможностью запускать 2 потока на ядро (16 логических потоков). Для представленных результатов моделировались центральные (или с минимальным отклонением) Au-Au UrQMD соударения при энергии 25 АГзВ. На рис. 5 представлены результаты исследования зависимости количества обработанных событий в секунду от числа запущенных потоков и от количества обработанных событий в каждом потоке. При максимальном использовании ресурсов компьютера (16 запущенных потоков) алгоритм позволяет обрабатывать более 1800 центральных событий в секунду (500 мкс/событие) и около 8000 событий с минимальным отклонением (125 мкс/событие).

1 evlhread •Q-10 ev./thread ■jAj. 100 evVthread

6 8 10 12 14 16 nof threads

4 6 8 10 12 14 16

nof threads

Рис. 5. Количество обработанных событий в секунду в зависимости от числа потоков (слева) и выигрыш, нормированный на время просчета для одного потока. Показаны результаты для различного количества событий в каждом потоке

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

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

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

2. Реализованы алгоритмы оценки параметров колец в RICH детекторе: 1) подгонка отсчетов окружностью, основанная на методе СОР и 2) подгонка отсчетов эллипсом, основанная на методе Таубина.

3. Разработан быстрый параллельный алгоритм реконструкции колец с использованием векторизации и многопоточности. Параллельный алгоритм показал одинаковую эффективность по сравнению с последовательным (начальным) алгоритмом, однако скорость работы выросла в 143 раза, учитывая проведенную оптимизацию.

4. Разработан новый алгоритм идентификации электронов в RICH детекторе, основанный на применении ИНС. Алгоритм показал двукратное преимущество в подавлении пионов по сравнению со стандартными методами.

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

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

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

1. Лебедев С., Ососков Г. Быстрые алгоритмы распознавания колец и идентификации электронов в детекторе RICH эксперимента СВМ // Письма в ЭЧАЯ. 2009. Т. 6, № 2(151). С. 260-284.

2. Höhne С., Lebedev S. et al. Development of a RICH detector for electron identification in CBM // Nuclear Inst, and Methods in Physics Research, A. 2008. Vol. 595. Pp. 187-189. doi:10.1016/j.nima.2008.07.029.

3. Lebedev S., Hohne C., Ososkov G. Fast Ring Recognition in the RICH detector of the CBM Experiment at FAIR // Вестник РУДН Серия Математика, информатика, физика. 2010. X' 3(2). С. 77-80.

4. Айриян А. С., Иванов В. В., Лебедев С. А. и др. Методы оценки параметров колец че-ренковского излучения в детекторе RICH для эксперимента СВМ // Вестник РУДН Серия Математика, информатика, физика. 2010. Xs 2(2). С. 124-131.

5. Lebedev A., Lebedev S., Ososkov G. Pattern recognition methods for data handling of the CBM experiment // JINR Comunication 10,11-2010-22. 2010. Pp. 191-201.

6. Lebedev S., Hohne C., Ososkov G. Ring Recognition and Electron Identification in the RICH detector of the CBM Experiment at FAIR // J. Phys.: Conf. Ser. 2010. Vol. 219 032015. doi: 10.1088/1742-6596/219/3/032015.

7. 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.

8. Lebedev S., Ososkov G., Hohne C. Ring recognition in the CBM RICH detector // CBM-RICH-note-2008-001. 2008. URL: https://www.gsi.de/documents/ DOC-2008-Jan-29.html.

9. Lebedev S., Ososkov G., Hohne C. Ring Recognition in the CBM RICH detector // JINR Communication E10-2007-88. 2007.

10. Lebedev S. Fast Parallel Ring Recognition Algorithm in the RICH Detector of the CBM Experiment at FAIR // JINR Communication E10-2011-5. 2011.

11. Lebedev S., Ososkov G. Ring Recognition in CBM RICH detector // LIT Scientific Report 2006-2007. 2007. Pp. 107-108.

12. Ayriyan A., Chernov N., Lebedev S. et al. Two methods for ellipse fitting in the CBM experiment // LIT Scientific Report 2008-2009. 2009. Pp. 52-53.

13. Ayriyan A., Chernov N., Ivanov V. et al. Taubin based ellipse fitting algorithm for CB-M-RICH at FAIR // CBM Progress Report 2009. 2010. P. 80.

14. Lebedev S., Hohne C., Ososkov G. Fast parallel ring reconstruction algorithm for the RICH detector in the CBM experiment // GSI Scientific Report 2009. 2010. P. 79.

15. Lebedev S., Hohne C., Ososkov G., Uhlig F: Systematic investigations of RICH and TRD detector parameters on electron identification in the CBM experiment // GSI Scientific Report 2009. 2010. P. 81.

16. Lebedev S., Belolaptikova E., Hohne C. Layout study of the RICH detector in the CBM experiment // CBM Progress Report 2008. 2009. P. 20.

17. Lebedev S., Hohne C., Ososkov G. Electron identification in the CBM experiment // CBM Progress Report 2008. 2009. P. 84.

18. Lebedev S., Ososkov G. Ring recognition in the CBM RICH detector // GSI Scientific Report 2007. 2008. P. 21.

19. Hohne C., Maevskaya A., Lebedev S. et al. Electron identification and Jjip detection in CBM // GSI Scientific Report 2006. 2007. P. 13.

20. Hohne C., Gorbunov S., Kisel I. et al. Simulation studies of electron identification with the RICH detector for CBM // GSI Scientific Report 2005. 200G. P. 63.

21. Ayriyan A., Chernov N., Lebedev S., Ososkov G. Two methods of ellipse fitting in the CBM experiment // Сборник трудов XIII конференции молодых ученых и специалистов. 2009.

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

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

24. Лебедев С., Ососков Г. Поиск колец черепковского излучения в RICH детекторе // Сборник трудов X конференции молодых ученых и специалистов. 2006.

25. Лебедев С., Айриян А., Лебедев А., Ососков Г. Поиск целеуказаний в RICH детекторе, основанный на методе преобразования Хафа // Сборник трудов IX конференции молодых ученых и специалистов. 2005.

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

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

A2. Höhne С., Rami F., Staszel P. // Nucl. Phys. News. 2006. Vol. 16 1. Pp. 19-23.

A3. Baur R. et al. // Nuclear Inst, and Methods in Physics Research, A. 1994. Vol. 343.

A4. Müller U. et al. // Nuclear Inst, and Methods in Physics Research, A. 1994. Vol. 343. Pp. 279-283.

A5. Bächler J. et al. // Nuclear Inst, and Methods in Physics Research, A. 1994. Vol. 343. Pp. 273-275.

A6. Mauro A. D. et al. // Nuclear Inst, and Methods in Physics Research, A. 1994. Vol. 343. Pp. 284-287.

A7. Seguinot J., T.Ypsilantis // Nuclear Inst, and Methods in Physics Research, A. 1994. Vol. 343. Pp. 1-29.

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

A9. GEANT — Detector Description and Simulation Tool, CERN Program Library Long Writeup W5013. 1993.

A10. Bertini D., Al-Turany M., Konig I., Uhlig F. The FAIR simulation and analysis framework // J. Phys.: Conf. Ser. 2008. Vol. 119.

All. Chernov N., Ososkov G. Effective Algorithms for Circle Fitting // Comp. Phys. Comm. 1984. Vol. 33. Pp. 329-333.

A12. Pratt V. Direct Least-Squares Fitting of Algebraic Surfaces // Comp. Graphics. 1987. Vol. 21. Pp. 145—-152.

A13. Minuit User's Guide. URL: http://lcgapp.cern.ch/project/cls/work-packages/ mathlibs/minuit/index.html.

A14. Taubin G. // IEEE Trans. Pattern Analysis Machine Intelligence. 1991. Vol. 13. Pp. 1115-1138.

А15. Chernov N. // Journal of Mathematical Imaging and Vision. 2007. Vol. 27. Pp. 231-239.

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

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

Получено 8 февраля 2011 г.

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

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

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

Введение

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

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

1.2. Обзор установки.

1.3. Задача идентификации электронов.

1.4. Детектор черепковского излучения RICH.

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

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

2.1. Введение.

2.2. Итерационный метод.

2.3. Отношения функций максимального правдоподобия

2.4. Сравнения с эталонным изображением (метод масок).

2.5. Нечеткая кластеризация.

2.6. Эластичная нейронная сеть.

2.7. Преобразование Хафа.

2.8. Выводы.

Глава 3. Алгоритмы реконструкции колец черенковского излучения и идентификации электронов в RICH детекторе эксперимента СВМ.

3.1. Введение.

3.2. Алгоритм локального поиска колец.

3.3. Оценка параметров колец черенковского излучения.

3.4. Глобальный отбор колец.

3.5. Идентификация электронов в RICH детекторе.

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

3.7. Оптимизация детектора RICH.

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

3.9. Выводы.

Глава 4. Применение параллельных вычислений в алгоритме реконструкции колец черенковского излучения

4.1. Введение.

4.2. Оптимизация алгоритмов.

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

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

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

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

4.7. Выводы.

Актуальность работы. Работа посвящена одной из важных проблем экспериментальной физики высоких энергий (ФВЭ), а именно задаче реконструкции событий1, полученных в ядро-ядерных соударениях. Характерными особенностями многих современных экспериментов в физике высоких энергий являются большая множественность и плотность частиц в каждом событии (до 1000 зарегистрированных частиц в событии), а также высокая скорость поступления данных (до 107 событий/сек.). Для анализа полученных данных необходимы быстрые и эффективные алгоритмы и программы.

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

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

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

Одной из основных задач в эксперименте СВМ является идентификация электронов2, которая необходима для реконструкции J/ф и ф' мезонов и легких векторных мезонов (р, ш, ф) при распаде по диэлектронному каналу. С одной стороны, требуется хорошая эффективность идентификации электронов, с другой стороны, необходимо хорошее подавление пионов, так как они составляют основной фон при физическом анализе. Для идентификации электронов и подавления пионов будут использованы детектор черенковского излучения RICH (Ring Imaging CHerenkov) и детектор переходного излучения TRD (Transition Radiation Detector).

Детекторы RICH широко применяются во многих экспериментах в физике высоких энергий как часть системы идентификации частиц (см., например, [3-6] и обзор [7]). Принцип работы RICH детектора основан на том, что при прохождении частицы в среде, характеризуемой показателем преломления п, со скоростью V, превышающей скорость света в данной среде, испускается че-ренковское излучение под углом В к траектории движения частицы, при этом cosB = 1/ßn, где ß ~ v/c. Угол В зависит от типа частицы и ее импульса. В RICH детекторах черенковские фотоны регистрируются напрямую фотодетектором (или фокусируются сферическим зеркалом на фотодетектор) в виде изображения колец. Скорость заряженной частицы определяется по радиусу кольца, на котором располагаются фотоны, в соответствии с конструкцией и оптической системой детектора. RICH детектор часто используется для идентификации частиц совместно с детектором для измерения импульса, так как совокупность информации о скорости и импульсе частицы позволяет определить ее массу, по которой она может быть идентифицирована. Для определения угла, под которым испускается черепковское излучение, необходимо распознать и оценить параметры колец. Поэтому реконструкция колец в событиях является важной задачей для всех RICH детекторов.

2 Здесь и далее предполагается идентификация электронов и позитронов.

В диссертации представлены алгоритмы реконструкции событий в RICH детекторе эксперимента СВМ. К этим алгоритмам предъявляются следующие требования: 1) высокая скорость работы алгоритмов из-за необходимости обрабатывать большой поток данных, 2) высокая эффективность распознавания колец, 3) устойчивость вычислений к обработке событий с большой множественностью частиц. Проведенный анализ показал, что существующие алгоритмы не удовлетворяют таким требованиям по эффективности и/или скорости работы. Поэтому возникла необходимость развития существующих и разработки новых, более эффективных алгоритмов. Одним из способов ускорения процесса обработки являются параллельные вычисления. Современная архитектура процессоров развивается по пути увеличения количества вычислительных ядер и применения векторных вычислений, что позволяет существенно повысить эффективность работы программ при использовании параллельных алгоритмов.

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

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

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

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

2. разработать эффективный алгоритм идентификации электронов в RICH детекторе;

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

4. реализовать алгоритмы в программной оболочке эксперимента СВМ — CBMROOT, и выполнить их тестирование;

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

6. провести исследования по оптимизации конструкции RICH детектора и выработать требования по ее улучшению.

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

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

2. Предложен и программно реализован оригинальный критерий оценки качества найденных колец, основанный на применении искусственной нейронной сети (ИНС). На основе этого критерия разработана процедура отбора колец из массива кандидатов, найденных программой распознавания. Процедура удаляет ложные кольца без потери эффективности распознавания.

3. Разработан новый алгоритм идентификации электронов в RICH детекторе, основанный на применении ИНС. Алгоритм показал двукратное преимущество в подавлении пионов по сравнению с ранее известными алгоритмами.

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

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

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

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

1. Разработанное программное обеспечение включено в общую программную оболочку эксперимента СВМ — CBMROOT [10], и активно используется членами коллаборации СВМ. Программы применялись как на стадии развития эксперимента и его физического обоснования, так и для оптимизации создаваемой экспериментальной установки. Результаты, полученные с использованием созданных алгоритмов и программ, подтвердили необходимый уровень идентификации электронов и подавления пионов.

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

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

4. Алгоритмы распознавания и оценки параметров колец, разработанные в диссертации, имеют самостоятельную научную ценность и могут быть использованы в других областях науки (биологии, медицине).

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

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

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

3. Разработан алгоритм идентификации электронов в RICH детекторе, основанный на применении искусственной нейронной сети. Алгоритм показал двукратное преимущество в подавлении пионов по сравнению с ранее известными алгоритмами.

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

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

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

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

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

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

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

- Advanced Computing and Analysis Techniques in Physics Research (ACAT10) (Индия, 2010);

• на семи международных совещаниях коллаборации СВМ в 2006 - 2010 годах;

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

• на двух конференциях немецкого физического общества (Дармштадт, 2008; Бонн, 2010);

• а также на научных семинарах в Лаборатории информационных технологий ОИЯИ и на совещаниях СВМ группы в СБГ (Дармштадт, Германия).

Публикации. По материалам диссертации опубликовано 25 работ [1135], в том числе 4 работы из Перечня ВАК [11-14].

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

Структура и объем диссертации. Диссертационная работа состоит из Введения, 4 глав, Заключения, содержит 94 страницы, 41 иллюстрацию и список литературы из 64-х пунктов.

4.7. Выводы

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

2. Исследовано распараллеливание на уровне событий.

Заключение

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

2. Реализованы алгоритмы оценки параметров колец в RICH детекторе: 1) подгонка отсчетов окружностью, основанная на методе СОР и 2) подгонка отсчетов эллипсом, основанная на методе Таубина.

3. Разработан быстрый параллельный алгоритм реконструкции колец с использованием векторизации и мпогопоточности. Параллельный алгоритм показал одинаковую эффективность по сравнению с последовательным (начальным) алгоритмом, однако скорость работы выросла в 143 раза, учитывая проведенную оптимизацию.

4. Разработан новый алгоритм идентификации электронов в RICH детекторе, основанный на применении ИНС. Алгоритм показал двукратное преимущество в подавлении пионов по сравнению со стандартными методами.

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

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

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

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

2. Hohne C., Rami F., Staszel P. // Nucl. Phys. News. 2006. Vol. 16 1. Pp. 19-23.

3. Baur R. et al. // Nuclear Inst, and Methods in Physics Research, A. 1994. Vol. 343.

4. Miiller U. et al. // Nuclear Inst, and Methods in Physics Research, A. 1994. Vol. 343. Pp. 279-283.

5. Bachler J. et al. // Nuclear Inst, and Methods in Physics Research, A. 1994. Vol. 343. Pp. 273-275.

6. Mauro A. D. et al. // Nuclear Inst, and Methods in Physics Research, A. 1994. Vol. 343. Pp. 284-287.

7. Seguinot J., T.Ypsilantis // Nuclear Inst, and Methods in Physics Research, A. 1994. Vol. 343. Pp. 1-29.

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

9. GEANT — Detector Description and Simulation Tool, CERN Program Library Long Writeup W5013. 1993.

10. Bertini D., Al-Turany M., Konig I., Uhlig F. The FAIR simulation and analysis framework // J. Phys.: Conf. Ser. 2008. Vol. 119.

11. Лебедев С., Ососков Г. Быстрые алгоритмы распознавания колец и идентификации электронов в детекторе RICH эксперимента СВМ // Письма в ЭЧАЯ. 2009. Т. 6, № 2(151). С. 260-284.

12. Holme С., Lebedev S. et al. Development of a RICH detector for electron identification in CBM // Nuclear Inst, and Methods in Physics Research, A. 2008. Vol. 595. Pp. 187-189. doi:10.1016/j.nima.2008.07.029.

13. Lebedev S., Hohne C., Ososkov G. Fast Ring Recognition in the RICH detector of the CBM Experiment at FAIR // Вестник РУДН Серия Математика, информатика, физика. 2010. № 3(2). С. 77-80.

14. Айриян А. С., Иванов В. В., Лебедев С. А. и др. Методы оценки параметров колец черенковского излучения в детекторе RICH для эксперимента СВМ // Вестник РУДН Серия Математика, информатика, физика. 2010. № 2(2). С. 124-131.

15. Lebedev A., Lebedev S., Ososkov G. Pattern recognition methods for data handling of the CBM experiment // JINR Comunication 10,11-2010-22. 2010. Pp. 191-201.

16. Lebedev S., Hohne C., Ososkov G. Ring Recognition and Electron Identification in the RICH detector of the CBM Experiment at FAIR // J. Phys.: Conf. Ser. 2010. Vol. 219 032015. doi:10.1088/1742-6596/219/3/032015.

17. 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.

18. Lebedev S., Ososkov G., Hohne C. Ring recognition in the CBM RICH detector // CBM-RICH-note-2008-001. 2008. URL: https://www.gsi.de/ documents/D0C-2008-Jan-29.html.

19. Lebedev S., Ososkov G., Hohne C. Ring Recognition in the CBM RICH detector // JINR Communication E10-2007-88. 2007.

20. Lebedev S. Fast Parallel Ring Recognition Algorithm in the RICH Detector of the CBM Experiment at FAIR // JINR Communication E10-2011-5. 2011.

21. Lebedev S., Ososkov G. Ring Recognition in CBM RICH detector // LIT Scientific Report 2006-2007. 2007. Pp. 107-108.

22. Ayriyan A., Chernov N., Lebedev S. et al. Two methods for ellipse fitting in the CBM experiment // LIT Scientific Report 2008-2009. 2009. Pp. 52-53.

23. Ayriyan A., Chernov N., Ivanov V. et al. Taubin based ellipse fitting algorithm for CBM-RICH at FAIR // CBM Progress Report 2009. 2010. P. 80.

24. Lebedev S., Höhne C., Ososkov G. Fast parallel ring reconstruction algorithm for the RICH detector in the CBM experiment // GSI Scientific Report 2009. 2010. P. 79.

25. Lebedev S., Höhne C., Ososkov G., Uhlig F. Systematic investigations of RICH and TRD detector parameters on electron identification in the CBM experiment // GSI Scientific Report 2009. 2010. P. 81.

26. Lebedev S., Belolaptikova E., Höhne C. Layout study of the RICH detector in the CBM experiment // CBM Progress Report 2008. 2009. P. 20.

27. Lebedev S., Höhne C., Ososkov G. Electron identification in the CBM experiment // CBM Progress Report 2008. 2009. P. 84.

28. Lebedev S., Ososkov G. Ring recognition in the CBM RICH detector // GSI Scientific Report 2007. 2008. P. 21.

29. Höhne C., Maevskaya A., Lebedev S. et al. Electron identification and J/-0 detection in CBM // GSI Scientific Report 2006. 2007. P. 13.

30. Hohne С., Gorbunov S., Kisel I. et al. Simulation studies of electron identification with the RICH detector for CBM // GSI Scientific Report 2005. 2006. R 63.

31. Ayriyan A., Chernov N., Lebedev S., Ososkov G. Two methods of ellipse fitting in the CBM experiment // Сборник трудов XIII конференции молодых ученых и специалистов. 2009.

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

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

34. Лебедев С., Ососков Г. Поиск колец черенковского излучения в RICH детекторе // Сборник трудов X конференции молодых ученых и специалистов. 2006.

35. Лебедев С., Айриян А., Лебедев А., Ососков Г. Поиск целеуказаний в RICH детекторе, основанный на методе преобразования Хафа // Сборник трудов IX конференции молодых ученых и специалистов. 2005.

36. URL: http: //hamamatsu. com.

37. ROOT — An Object-Oriented Data Analysis Framework. URL: http:// root.cern.ch.

38. The Virtual Monte Carlo (VMC). URL: http://root.cern.ch/drupal/ content/vmc.

39. Nuclear Inst, and Methods in Physics Research, A. 2003. Vol. 506. Pp. 250-303.

40. Ferrari A., Sala P., Fasso A., Ranft J. FLUKA:a multi-particle transport code. URL: http://fluka.org.

41. Fröhlich I. et al. Pluto: A Monte Carlo Simulation Tool for Hadronic Physics // PoS. 2007. Vol. ACAT2007. P. 76.

42. Staric M., Krizan P. An Iterative Method for the analysis of Cherenkov rings in the HERA-B RICH // Nuclear Inst, and Methods in Physics Research, A. 1999. Vol. 433. Pp. 279-285.

43. HERA-B experiment. URL: http://www-hera-b.desy.de.

44. Schöning A. Particle identification in the RICH detector and study of impact parameters // LHCb note. 1997. Vol. LHC-B/97-018.

45. Forty R., O.Schneider. RICH pattern recognition // LHCb note. Vol. LHCb-98-040.

46. Gath I., Hoory D. Fuzzy clustering of elliptic ring-shaped clusters // Pattern recognition Letters. 1995. Vol. 16. Pp. 727-741.

47. Krishnapuram R., Keller J. M. A possibilistic approach to clustering // IEEE Transactions on Fuzzy systems. 1993. Vol. 1, no. 2.

48. Krishnapuram R., Keller J. M. The possibilistic C-Mean algorithm Insights and recomendations // IEEE Transactions on Fuzzy systems. 1996. Vol. 4, no. 3.

49. Massone A., Studer L. Pattern recognition in RICH counters using the possibilistic C-Spherical shell algorithm // IEE&IEEE. 2000. Pp. 792-795. Proc.of the 4th Intl. Conf. on Knowledge-based intelligent engineering systems and allied technologies.

50. Gorbunov S., Kisel I. Elastic net for stand-alone RICH ring finding // Nuclear Inst, and Methods in Physics Research, A. 2006. Vol. 559. Pp. 139-142.

51. Gorbunov S., Kisel I. Elastic net for standalone RICH ring Finding // CBM note. 2005. Vol. CBM-SOFTnote-2005-002.

52. Durbin R., Willshaw D. An Analogue Approach to the Travelling Salesman Problem Using an Elastic Net Method // Nature. 1987. Vol. 326.

53. Hough P. V. C. Method and Means for Recognizing Complex Patterns. 1962.

54. Radon J. Uber die Bestimmung von Funktionen durch ihre Integral werte längs gewisser Mannigfaltigkeiten. 1917. Pp. 262-277.

55. Toft P. The Radon Transform Theory and Implementation: Ph.D. thesis / Department of Mathematical Modelling, Technical University of Denmark. 1996.

56. Chernov N., Ososkov G. Effective Algorithms for Circle Fitting // Comp. Phys. Comm. 1984. Vol. 33. Pp. 329-333.

57. Pratt V. Direct Least-Squares Fitting of Algebraic Surfaces // Comp. Graphics. 1987. Vol. 21. Pp. 145—152.

58. Minuit User's Guide. URL: http://lcgapp.cern.ch/project/cls/ work-packages/mathlibs/minuit/index.html.

59. Crawford J. A Non-Iterative Method for Fitting Circular Arcs to Measured Points // Nucl. Instr. Methods Phys. Res. 1983. Vol. 211. Pp. 223—225.

60. Taubin G. // IEEE Trans. Pattern Analysis Machine Intelligence. 1991. Vol. 13. Pp. 1115-1138.

61. Chernov N. // Journal of Mathematical Imaging and Vision. 2007. Vol. 27. Pp. 231-239.

62. Koszon P. et al. Investigation of wavelength shifter properties of p-terphenyl and TPB // CBM Progress Report 2008. 2009. P. 26.

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

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