Data Mining and Data Analysis Methods G.A.Ososkov, Laboratory of Information Technologies Joint Intstitute for Nuclear Research, 141980 Dubna, Russia email: - презентация

1 Data Mining and Data Analysis Methods G.A.Ososkov, Laboratory of Information Technologies Joint Intstitute for Nuclear Research, Dubna, Russia SCHOOL ON JINR/CERN GRID AND ADVANCED INFORMATION SYSTEMS, Dubna, November

2 Data handling on the LHC experiments 2 БАК в 2012 г. ALICEALICE, ALICE, ALICE ATLASATLAS, ATLAS, ATLAS CMS LHCb один петабайт = байт данных/сек Запомнить такое количество данных невозможно ни на какой из современных вычислительных систем Система триггеров разных уровней выполняла сверхбыструю сложную электронную предобработку, оставлявшую только одно полезное физическое событие из 10 тысяч Дальнейший анализ выполнялся в ЦЕРНовском компьютерном центре обработки из многих тысяч процессоров. Оставалось только 1% событий, возможно содержащих искомый физический феномен. Сокращение в миллион раз! которые требовалось хранить в специальных Итог - 25 петабайт данных в год, которые требовалось хранить в специальных роботизированных ленточных хранилищах, т.к. копии этих данных подлежат передаче в сотни физических центров 36 стран мира для более тщательного анализа Идея распределенной обработки G.Ososkov AIS-GRID : только ATLAS выдает 2 PtB/sec!

3 WLCG - Worldwide LHC Computing Grid - Worldwide LHC Computing Grid (WLCG). Сотни тысяч компьютеров, объединены во Всемирную сеть распределенных вычислений - Worldwide LHC Computing Grid (WLCG).Worldwide LHC Computing GridWorldwide LHC Computing Grid Иерархическая структура WLCG состоит из вычислительных Tier-центров разных уровней. Ежедневно в WLCG обрабатываются полтора миллиона заданий. 3 Создание баз хранение их копий Создание баз наблюденных и смоделированных данных и хранение их копий (реплик) Распространение и обмен репликами Распространение и обмен репликами по запросам WLCG центров разных уровней. процесс копирования и стирания устаревших записей Сбалансированны й процесс копирования востребованных и стирания устаревших записей Помимо задач анализа данных значительную часть занимают задачи хранения и обмена данными в системе WLCG G.Ososkov AIS-GRID 2015

4 Data-intensive science - the new paradigm назвал грид- технологии одним из трех столпов успеха На торжестве 4 июля 2012 г. по поводу получения ЦЕРНом нобелевской премии за открытие бозона Хиггса директор ЦЕРНа Рольф Хойер прямо назвал грид- технологии одним из трех столпов успеха (наряду с ускорителем LHC и физическими установками). 4 Известный специалист MicroSoft в области хранения информации Джим Грэй предсказал, в 2005 г., что вступление научных исследований в эпоху пета- и экзо-данных должно неизбежно потребовать развития новой науки с интенсивной обработкой (Data-intensive science) и назвал это изменение «четвертой парадигмой науки», в дополнение к трем предыдущим научным парадигмам экспериментальной, теоретической и вычислительной Этот успех также подтверждает, что ЦЕРН входит в эру Больших Данных и эффективно преодолевает проблемы четвертой парадигмы, что является одним из примеров (наряду с созданием в ЦЕРНе WWW-всемирной паутины), когда разработки в области физики частиц начинают влиять на исследования в других научных областях. G.Ososkov AIS-GRID 2015

5 Where is high energy and nuclear physics in Big Data terms? 5 We are BIG! Сравнительная диаграмма по общим объемам перерабатываемых в 2012 году данных в социальных сетях, поисковых системах, разных отраслях бизнеса, медицины, климатических прогнозов и БАК наглядно показывает, что исследования в ЦЕРНе идут в условиях Больших Данных Более того, в результате вторичного запуска модернизированного БАК в 2015 году поток данных возрос в 2,5 раза при удвоении времени на их обработку. G.Ososkov AIS-GRID 2015

6 Определения Больших Данных Простое определение велики и сложны стандартными средствами доступных баз данных и иных имеющихся систем хранения, передачи и обработки Простое определение: Большие Данные те, что слишком велики и сложны, чтобы их можно было эффективно запомнить, передать и проанализировать стандартными средствами доступных баз данных и иных имеющихся систем хранения, передачи и обработки. «три V»: Кроме объема, следует учитывать и другие их характеристики. Еще в 2001 году Мета Групп ввела в качестве определяющих характеристик для больших данных так называемые «три V»: объём (volume) объём (volume), в смысле величины физического объёма), скорость (velocity) скорость (velocity) в смыслах как скорости прироста, так и необходимости высокоскоростной обработки и получения результатов), многообразие (variety) многообразие (variety), в смысле возможности одновременной обработки различных типов структурированных и неструктурированных данных общий поток данных растет экспоненциально, удваиваясь каждый год, Однако, когда общий поток данных растет экспоненциально, удваиваясь каждый год, за счет революционных технологических изменений, в 2014 году даже эту "3V" модель предлагали расширить, добавляя новые и новые «V», o Validity (обоснованность, применимость), o Veracity (достоверность), o Value (ценность, полезность), o Visibility (обозримость, способность к визуализации) и т. д. 6 G.Ososkov AIS-GRID 2015

7 7 Data Mining для работы с Big Data Data Mining (DM) - Это технология, которая предназначена для поиска в больших объемах данных неочевидных, объективных и полезных на практике закономерностей. Григорий Пятецкий-Шапиро, 1989 г. Переводы DM на русский: добыча данных, вскрытие данных, информационная проходка путем комбинации методов статистики и искусственного интеллекта с использованием технологии баз данных. Интеллектуальный анализ данных это процесс обнаружения в сырых данных ранее неизвестных, нетривиальных, практически полезных и доступных интерпретации знаний, необходимых для принятия решений в различных сферах человеческой деятельности путем комбинации методов статистики и искусственного интеллекта с использованием технологии баз данных. В современных условиях данных слишком много, они неоднородны, неполны, неструктурированны и содержат ошибки, а какой-либо рациональной теории для их описания, как правило, нет. к новой парадигме В современных условиях данных слишком много, они неоднородны, неполны, неструктурированны и содержат ошибки, а какой-либо рациональной теории для их описания, как правило, нет. Поэтому происходит сдвиг парадигмы их обработки от классической схемы моделирования на основе известной теории, а затем проверки модели сравнением с экспериментом традиционными средствами анализа данных к новой парадигме, когда модели, описывающие связи и зависимости создаются непосредственно из самих данных новыми средствами Data Mining. Одно из основных положений Data Mining – поиск неочевидных закономерностей. Инструменты Data Mining могут находить такие закономерности самостоятельно и также самостоятельно строить гипотезы о взаимосвязях. G.Ososkov AIS-GRID 2015

8 Кластеризация – важный инструмент Data Mining In many fields of todays science – biology, physics, geology, etc researchers deal with big data when the amount of input data is especially large (10 6 and more). Besides the feature space has many dimensions and there is no preliminary information about the number and locations of the sought-for regions. Therefore known clustering methods like k-means are hard to apply. 8 Новый двухэтапный подход в кластеризации In the first step the data undergoes intermediate clustering producing clusters which number is much smaller than the number of original objects. For clustering on the first step we choose Voronoi partition. It divides the vector space in set of convex polyhedrons so that each point in such polyhedron is closer to its center then to any other polyhedron center. Keep in mind: the Voronoi cells depend significantly on the metric used. One example. Estimation of the number of customers of a given shop by the nearest distance considerations. When customers go to the shop on foot by shortest way, Euclidean distance is used, but if they go by a vehicle according to street directions and traffic, then a more realistic distance function will be the Manhattan distance Voronoi cells for Euclidean distance Voronoi cells for Manhattan distance G.Ososkov AIS-GRID 2015

9 Связь триангуляции Делоне и Разбиений Вороного The Delaunay triangulation corresponds to the Voronoi diagram in a one-to-one manner: the triangulation links the reference vectors whose Voronoi regions have common boundaries 9. Formation of a Voronoi diagram on a plane: (i) nods on the plane, (ii) Delaunay triangulation, (iii) Voronoi diagram, (iv) superposition of the Delaunay triangulation and the resulting Voronoi diagram. S.V. Mitsyn, G.A. Ososkov, The Growing Neural Gas and Clustering of Large Amounts of Data, Optical Memory and Neural Networks (Information Optics), 2011, Vol. 20, No. 4, pp. 260–270 Как это работает методом Растущего Нейронного Газа An example of objects to be partitioned into Voronoi mosaic source data ( 2 million points ) Delaney triangulation Voronoi mosaic (100 сеlls only) source data ( 2 million points ) Delaney triangulation Voronoi mosaic (100 сеlls only) The problem of image quantization is just inverse one, when Delaney triangulation is unknown, we are looking for centers of Voronoi mosaic G.Ososkov AIS-GRID 2015

10 Второй этап кластеризации Второй этап кластеризации Final clustering – many known algorithms: single linkage, Ward method etc. Newest study - by watershed algorithm Results of watershed clustering. Initial distributions 10 watershed as geodesic reconstruction G.Ososkov AIS-GRID 2015 Thanks to Sergey Mitsyn

11 Example. Clustering of geophysical data 11 Исходные данные: Вверху – магнитные измерения Внизу - гравитационные G.Ososkov AIS-GRID 2015

12 Методы Data Mining Непосредственное использование данных: дескриптивный анализ и описание исходных данных, кластерный анализ Статистические методы: анализ связей (корреляционный и регрессионный анализ, факторный анализ, дисперсионный анализ). Анализ временных рядов (динамические модели и прогнозирование). Методы искусственного интеллекта : искусственные нейронные сети (распознавание, кластеризация, принятие решений, прогноз); генетические алгоритмы; ассоциативная память (поиск аналогов, прототипов); нечеткая логика; деревья решений; системы обработки экспертных знаний. Хотя методы DM ориентированы главным образом на «майнинг» в бизнесе и социальных науках, они также часто применяются и в таких технических и научных областях, как биоинформатика, генетика, медицина, образование и электроэнергетические расчеты. Существует большой объем прикладных DM- программ в открытом, но больше – в коммерческом доступе. Однако DM-приложений для экспериментальной физики вы там не найдете. Чтобы понять, почему - посмотрим на некоторые эксперименты в физике высоких энергий (ФВЭ) и то, какие данные в них получаются 12 G.Ososkov AIS-GRID 2015

13 Эксперименты в Германии и Италии Эксперимент OPERA: поиск осцилляций нейтрино 13 OPERA Condensed Barion Matter schematic view of the СВМ setup CERN LNGS 730 km 1600 m in depth ~ m 3 caverns volume СВМ experiment СВМ experiment (Germany, GSI, to be running in 2018) 10 7 events per sec, ~1000 tracks per event ~100 numbers per track Total: terabytes/sec ! Condensed Barion Matter G.Ososkov AIS-GRID 2015

14 14 Анализ данных в детекторах CBM Реконструкция событий 10 7 соб/сек, ~1000 треков/соб, ~100 чисел/трек Тера Байт/сек в режиме on-line! 1. Вершинный детектор STS Задачи трекинга в магнитном поле: Распознавание треков Вычисление их параметров Определение вторичных вершин для короткоживущих и нейтральных частиц Модельный вид Au+Au взаимодействия в STS 2. Детектор RICH Задачи по идентификации электронов и пионов: распознать все кольца вычислить их параметры с учетом шумовых отсчетов, перекрытия колец и оптических искажений, из-за которых кольца выглядят, как эллипсы стыковать кольца с треками, найденными в STS определить, какие треки порождены электронами Кольца черенковского излучения, зарегистрированные в детекторе RICH G.Ososkov AIS-GRID 2015

15 15 Трекер образован 31 стеной из эмульсионных кирпичей, перемежаемых решетками из 7-миметровых сцинтилляторов, снабженных электронными регистраторами. Основная задача анализа данных трекера – определение того конкретного кирпича, где произошло искомое событие осцилляции нейтрино. Треки прослеживаемые по точкам пересечения сцинтилляторов, засвеченных проходящими частицами, должны сходиться в вершину, которая и определяет искомый кирпич Анализ данных Анализ данных в эксперименте OPERA BSP Два типа событий OPERA с BSP Подлинная вершина Hadron shower axix Мы не рассматриваем вопросы сканирования эмульсии для поиска осцилляций нейтрино, т.к. это – отдельная задача G.Ososkov AIS-GRID 2015

16 16 Отличия DM и анализа данных в ФВЭ и ЯФ свой собственный всеохватывающий набор методов анализа данных (Data Analysis – DA), моделировать сложнейшие физические процессы, происходящие в экспериментальных установках Физики, захлестываемые потоками данных от экспериментов и моделирования физических процессов, разработали свой собственный всеохватывающий набор методов анализа данных (Data Analysis – DA), реализованный в известной программной платформе ROOT, на которой теперь основаны почти все программные оболочки – фреймворки большинства европейских экспериментов. В отличие от DM, методы DA в физике высоких энергий и ядерной физике используют выдающиеся достижения теоретической физики, дающие возможность успешно моделировать сложнейшие физические процессы, происходящие в экспериментальных установках при взаимодействиях частиц в каждом из детекторов и траекторий получившихся осколков в каждом из компонентов этих детекторов с учетом их материалов и магнитных полей. задачи хранения и обмена даннымиГРИД-облачной системе распределенных вычислений Методы DA – это только часть общего гигантского процесса манипулирования данными в современных экспериментах ФВЭ и ЯФ. Помимо задач анализа данных не менее значительную часть занимают задачи хранения и обмена данными в иерархической ГРИД-облачной системе распределенных вычислений, объединяющей Tier-центры разных уровней. Концепция использования распределенных облачных систем для хранения, распределения и обработки данных является общей для физиков и безнесменов о б щ е е р а з л и ч и е о б щ е е р а з л и ч и е G.Ososkov AIS-GRID 2015

17 17 Важнейший этап – предобработка включает Получение и сохранение данных: до применение алгоритмов DA данные, подлежащие исследованию должны быть зарегистрированы, преобразованы из отсчетов детекторов в формат обычных единиц измерений; Селекция данных: фильтрация от шума и несущественных измерений, не удовлетворяющих заданным условиям. Проверка этих условий выполняется системой «умных» тригеров разных уровней и ведет к сокращению объема данных на много порядков; Преобразование данных (калибровка и алайнмент) для перевода в формат подходящий для последующего анализа и хранения. Этапы процессов DA в ФВЭ и ЯФ 1 G.Ososkov AIS-GRID 2015

18 18 Следующие этапы можно суммировать как Распознавание образов для реконструкции событий: трекинг, нахождение вершин событий, распознавание колец черенковского излучения, а также выявление и удаление ложно распознанных объектов. Применяемые методы преобразования Хафа, клеточные автоматы, фильтр Калмана, искусственные нейронные сети, вейвлет-анализ и др. Оценивание физических параметров методы математической статистики; робастное оценивание Проверка гипотез отношения правдоподобия, нейросети усиленные алгоритмы машинного обучения (boosted decision trees - BDT). Моделирование выполняется на всех этапах анализа данных Этапы процессов DA в ФВЭ и ЯФ 2 далее будут даны примеры применения методов DA из практики ОИЯИ G.Ososkov AIS-GRID 2015

19 19 Этапы процессов DA в ФВЭ и ЯФ 3 Следует подчеркнуть очень важную роль моделирующих программ (таких как GEANT) на всех этапах анализа данных. Моделирование позволяет: Оптимизировать по деньгам, материалам и времени всю экспериментальную установку и разработать алгоритмы DA еще на стадии проектирования; Разработать и протестировать необходимую программную оболочку эксперимента; Рассчитать заранее все необходимые распределения, пороги для проверки гипотез и сгенерировать обучающие выборки для искусственных нейронных сетей. Оптимизировать структуру и необходимое оборудование запланированных детекторов, компьютерных средств и сетей, минимизируя стоимостные и временные затраты при заданной эффективности и точности работы детектора и надежности электронного оборудования; G.Ososkov AIS-GRID 2015

20 Методы обработки и принципы имитационного моделирования Из курса для магистров кафедры САУ университета «ДУБНА» «Современные Методы обработки Данных в Задачах Управления (СМОДЗУ)» задачник и тексты лекций можно найти на сайте gososkov.ru/ Uni-Dubna teaching materials Там же в /nec-2015 найдете данную лекцию G.Ososkov AIS-GRID

21 G.Ososkov AIS-GRID Программа курса СМОДЗУ 1. Моделирование случайных воздействий и статистический анализ сигналов Алгоритмы моделирования случайных последовательностей с заданными законами распределения. Их реализация на С++ Проверка качества моделей по статистическим критериям хи-квадрат и Колмогорова. 2. Подгонка зависимостей к данным измерений. Методы максимального правдоподобия (ММП) и Наименьших квадратов (МНК). Робастная подгонка к засоренным измерениям. 3. Монте-Карло интегрирование многомерных функций 4. Искусственные нейронные сети (ИНС) и клеточные автоматы. Решение задач на их применение 5. Вейвлет-анализ и его применение для обработки сигналов 6. Основные понятия теории систем массового обслуживания (СМО). Аналитические методы моделирования СМО и их применение для решения задач оптимизации СМО.

22 1. NA-45. Determination of the interaction vertex for only two coordinate planes The target consists of eight 25-μ gold discs. 700 track events in narrow angular acceptance and large number of noise counts did not allow to recognize individual tracks. Robust fitting iterations converged in five iterations, although initial approximation was roughly taken as the middle of the target region. Robust fitting applications Application examples 2. Opera. 2D weights for muon tracks and hadron showers. Fitting with 2D robust weights, which depend not only on distance of a point to the fitted track, but also on amplitudes of track hits G.Ososkov AIS-GRID

23 G.Ososkov AIS-GRID neural nets Main types of neural nets applied in HEP 1. Прямоточные ИНС Искусственный нейрон Два этапа работы многослойного персептрона (МСП): Обучение МСП для вычмсления весов методом обратного распространения ошибки (error backpropagation) E=Σ m Σ ij (y i (m) – z i (m) ) 2 min {wik} 2. После обучения МСП с полученными весами используется, как подпрограмма, или зашивается в интегральную схему (neurochip) для очень быстрого выполнения Выход i-го нейрона h i =g(Σ j w ij s j ) Функция активации g(x)=1/(1+exp(-λx)) 2. Полносвязные ИНС (сети Хопфилда) Применения Выделение трек-элементов для последующего слияния их в трек 2. Генератор случайных многомерных векторов 3. Клеточные автоматы Применения МСП: Триггеры всех уровней Идентификация частиц Выбор между физическими гипотезами Аппроксимации Прогнозирование Применения Ассоциативная память Распознавание треков метод сегментов роторные сети эластичные сети

24 Почему, собственно, многослойный персептрон? Там выход нейрона Σ k w jk x k равен скалярному произведению векторов X и W j. Но есть радиально-базисные сети (RBF), где выход нейрона равен расстоянию ρ(X,W j ) между ними. Чаще всего используют метрики: Σ j (x j – w ij ) 2 – квадрат эвклидова расстояния (окружности); d 2 (X,Wj ) = (X-W j ) -T -1 (X- W j ) T -расстояние Махаланобиса для случаев, когда известна ковариационная матрица пикселей (эллипсы). RBF-сеть имеет скрытый слой из радиальных нейронов с гауссовой поверхностью отклика и выходной слой с линейными функциями активации. Обучение RBF-сети – на порядок быстрее, но затраты подбор гауссианов сводят на нет все преимущества. Задача: разбить двумерное множество из точек 3-х цветов на 3 кластера RBF-сеть А.Стадника. Пороговая активационная функция, динамическое добавление нейронов в скрытом слое, отдельное обучение нейронов и слоев. Алгоритм обучения использует метод ближайшего соседа: (1) Берем случайную точку и строим кластер С из её соседей, входящих в тот же класс, в соответствии в выбранной метрикой (Махаланобис); (2) по ходу увеличивается радиус R кластера C и перевычисляется его центр тяжести пока не встречается элемент другого класса; (3) добавляем в скрытый слой нейрон с синаптическим весом равным C и порогом R; (4) повторяем процедуру с любым неиспользованным элементом и продолжаем до полного исчерпания обучающего множества. Гарантированы сходимость и конечность времени обучения.

25 Wavelet analysis applications in particle physics Wavelet analysis applications in particle physics 1 1. Brief wavelet introduction. Why it is different from Fourier-transform?, One-dimensional wavelet transform of the signal f(x) has 2D form, where the function is the wavelet, b is the displacement, and a is the scale. Continuous wavelet family named Gaussian wavelets can be obtained by differencing a gaussian Continuous wavelets are remarkably resistant to noise, An example of the signal with a localized high frequency part and considerable contamination G 2 wavelet spectrum of this signal Filtering results. Filtering results. Noise is removed and high frequency part perfectly localized G.Ososkov AIS-GRID The most known of them is usualy named the Mexican hat. but because of their non-orthogonality one obtains non-admissible signal distortions after inverse transform. So orthogonal discrete wavelets (DWT) are mostly applicable

26 26 Why do we need wavelets for handling invariant mass spectra? - -we need them when S/B ratio is << Smoothing after background subtraction without losing any essential information 2. resonance indicating even in presence of massive background 3. evaluating peak parameters from invariant mass spectrum Wavelet shrinking thanks to Anna Senger, CBM thanks to Alex Stadnik ω.ω. Wavelet G 2 transforms a gaussian g(x;A,x o,σ) into wavelet of the same order, but with parameters of that gaussian: It is true for any order n and leads to the idea of looking for the peak parameters directly in G 2 domain without its inverting G.Ososkov AIS-GRID 2015

27 27 Принципы имитационного моделирования Имитационное моделирование - это моделирование сложных систем, характеризуемых сложностью, многоуровневой иерархической структурой; наличием взаимосвязей элементов и самих уровней; стохастичностью процессов функционирования явлений, необходимоcтью сымитировать поведение системы во времени. Развитие имитационных моделей стало возможным только с появлением компьютеров, поэтому часто вместо имитационного говорят о компьютерном моделировании, хотя последнее – шире, т.к. включает также аналитические и вычислительные модели Структуры имитационных моделей: модель состоит из следующих составляющих: - компоненты (блоки и уровни); - переменные; - параметры; - функциональные зависимости переменных и уровней; - ограничения (на время, ресурсы, ошибки, риски); - целевые функции. Их два типа: - сохранить, т.е. обеспечить min потерь, риска, ошибки; - приобрести, т.е обеспечить max прибыли, эффективности, точности.

28 G.Ososkov AIS-GRID Этапы моделирования АНАЛИЗ анализ работы объекта для выделения его основных функций, обеспечивающих выполнение им своего предназначения; статистический анализ данных об объекте, определение их источника (данные о состоянии элементов объекта или данные, получаемые от него самого в процессе его работы), и их природы: детерминированные или стохастические. Для последних – проверка гипотезы об их распределении и оценка параметров этих распределений; СИНТЕЗ разработка идеализированной математической модели объекта, включающей основные процессы его функционирования с использованием методов упрощающей аппроксимации и линеаризации, если они не препятствуют достижению целевых условий; разработка соответствующей компьютерной модели, реализующей имитационные алгоритмы математической модели; ВЕРИФИКАЦИЯ и СОПРОВОЖДЕНИЕ проверка адекватности модели методами математической статистики; ее отладка; сопровождение.

29 HENP computing at the Big Data era Планы развития компьютинга в ЦЕРНе для обеспечения потенциально новой физики после запуска БАК в 2015 году 1. Значительное увеличение вычислительных мощностей и сетевых ресурсов хранения данных; 2. Развитие интеллектуальных средств динамического хранения данных; 3. Повышение эффективности WLCG путем синтеза грид и облачных технологий; 4. активизация использования распределенных параллельных вычислений 5. Совершенствования алгоритмических и программных средств анализа и моделирования; Такие же планы характерны для ведущих физических центров мира, в том числе и для ОИЯИ с его мегапроектом NICA и CMS Tier 1 в ЛИТ. Обсудим пункт 3 29 G.Ososkov AIS-GRID 2015

30 3. Combined grid and cloud access to increase WLCG efficiency Жесткая структура системы грид создавалась для интеграции уже существующих аппаратных и программных ресурсов, зафиксированных в системе, в то время как облачная структура распределенных вычислений оказывается более гибкой, используя виртуальные кластеры из виртуальных вычислителей. Примером уже имеющейся технологии, реализующей подобный синтез для работы с Большими Данными является система PanDA (Production and Distributed Analysis – обработка данных и распределенный анализ) эксперимента АTLAS на LHC. Сегодня PanDA развилась в систему BigPanda и уже работает в ОИЯИ для CMS Tier1 и российского мегапроекта NICA 30 Николай Кутовский,: Включение в грид облачных структур позволяет сократить время решения широкого круга задач в области физики высоких энергий и повысить эффективность использования ресурсов G.Ososkov AIS-GRID 2015 Суперкомпьютеры 15, 2013, стр.56 Разработка сложнейших грид-облачных систем сбора, передачи и распределённой обработки сверхбольших объемов информации требует больших предварительных исследований по выбору оптимальной их структуры с учетом стоимости и предполагаемых ресурсов и загрузки. Для оптимизации создаваемых систем их нужно моделировать

31 Simulation of grid and cloud systems потока ресурсовсостава моделируемой грид-структуры Исследования сложнейших грид-облачных систем сбора, передачи и распределённой обработки сверхбольших объемов информации должны основываться на тщательном моделировании как потока заданий с учетом их типов и статистических данных о распределении времени их поступления и требуемых компьютерных ресурсов для их выполнения, так и состава моделируемой грид-структуры. программа моделирования SyMSim (Synthesis of Monitorung and Simulation) разработана в ЛИТ ОИЯИ для оптимизации центра WLCG Tier 1 CMS и ускорения проектирования центров Tier 0/1 проекта NICA. Такая программа моделирования SyMSim (Synthesis of Monitorung and Simulation) разработана в ЛИТ ОИЯИ для оптимизации центра WLCG Tier 1 CMS и ускорения проектирования центров Tier 0/1 проекта NICA. Программа ориентирована на повышения эффективности их разработки путем учета качества работы уже функционирующей системы в прогнозах на ее дальнейшее развитие. Это выполнено за счет объединения самой программы моделирования с системой мониторинга реального (или модельного) грид-облачного сервиса через специальную базу данных, осуществляющую сбор и статистический анализ по вычислению распределений данных мониторинга, используемых затем для динамической коррекции параметров моделирования. 31 G.Ososkov AIS-GRID 2015

32 Basic simulation concepts The best way to evaluate dynamically the system functioning quality is using its monitoring tools The simulation program is to be combined with real monitoring system of the grid/cloud service through a special database (DB) To ensure a developer from writing the simulation program from zero on each development stage it is more feasible to accept a twofold model structure, when it consists from core 1. a core – its stable main part independent on simulated object and declarative module 2. a declarative module for input of model parameters defining a concrete distributed computing center, - its setup and parameters obtained from monitoring information, as dataflow, job stream, etc DB intention is just to realize this declarative module work and provide means for output of simulation results Web-portal is needed to communicate with DB assigning concrete simulation parameters and storing results in DB G.Ososkov AIS-GRID

33 How it was realized G.Ososkov AIS-GRID Our team has already the experience with simulation grid structures inspired by GridSim library ( and job scheduler ALEA ( The new simulation program called SyMSim (Synthesis of Monitoring and SIMulation) was developed according to the above basic concepts and succesfully tested for the JINR CMS Tier 1 center with robotized tape library. To accomplish that New classes are invented to declare the data store specific for the tape robot library; Input job stream is formed via data base; Data exchange process is modified from packet flow simulation into file transfer simulation; Software means for handling simulation results are provided.

34 Игровая модель центра хранения данных Рассматривается модель реализации компьютерного центра для хранении данных в роботизированной библиотеке с тысячами кассет с магнитными лентами, которые робот автоматически достаёт и устанавливает в одно или несколько устройств чтения-записи (драйвов). 34 Проектируемая структура: ленточный робот, массив драйвов, кластер процессоров. Стоимость драйва - 5 условных единиц, процессора - 3 единицы. Критерий оценки: время прохождения тестового потока из 100 заданий. Бюджет: 100 условных единиц Требования к проекту: оптимальное соотношение количества процессоров и количества драйвов в пределах бюджета Результаты моделирования. 1. Определение степени загрузки кластера Загрузка кластера W = T 100 /Tа, где T 100 –процессорное время выполнения пакета Ta – астрономическое время При большом количестве процессоров загрузка кластера падает, поскольку процессоры простаивают в ожидании монтирования кассет с данными на драйвы. надо Следовательно, надо выбирать оптимальное соотношение 2. Время выполнения пакета заданий в зависимости от количества процессоров и драйвов. Стрелкой показан оптимум по числу вычислительных процессоров в кластере и дорогих драйвов. Таким образом, конфигурация, обеспечивающая минимальное время исполнения должна состоять из 18 вычислительных процессоров и 9 драйвов G.Ososkov AIS-GRID 2015

35 Tier1 Dataflow simulation Site CBM Т0 at CERN The problem is to simulate a data storage system with robotized tape library, where RAW data are to be transferred from disks of a great HEP experiment. In reality we were charged to design such data storages for the CMS Tier 1 at JINR. How it works on T1 site: 1. From disk to tape: - If slot and file are available, job is executed at the farm; 2. From tape to disk: - If file stored in tape library. job reserves a slot, but is waiting job reserves a slot, but is waiting for necessary file on the disk: for necessary file on the disk: the robot moves tape cartridge to the drive, cartridge's file system mounting to the drive, file is copied to the disk. ss JINR T1 G.Ososkov AIS-GRID Scheme of the job and data flow at JINR Т1

36 CPU Disks TB these parameters from real T1 were set to the model Tapes - 5 PB Statistics was taken from G.Ososkov AIS-GRID JINR Tier 1 statistics obtained from monitoring ~ 2 mil. Submitted Jobs (2014) ~ 3 mil. Submitted Jobs (6 month of 2015)

37 Examples of Real and Generated Workflow X = S = 6700 Completed jobs (real) WallClock HEPSPEC06 (real) X = S = 8100 X = S = 6100 Completed jobs (simulated) WallClock HEPSPEC06 (simulated) X = S = 6400 G.Ososkov AIS-GRID Real and simulated distribution look similar in terms of the error corridors These two examples among some others were used for the positive validation of the running CMS T1 model and encouraged us to simulate the more sophisticate and planning yet the T0/T1 system of NICA project.

38 Simulation evolution: from CMS Tier1 to NICA Tier0-Tier1 Tier 0 module denotes the center of data gathering from the experiment (either MPD or SPD). Obtained raw data are to be stored on disks. One of planned problems is to recommend the volume of the disk store and a temp of data transfer to the robotized library which is the part of Tier 1 center. This two-level structure is interconnected by a local area network G.Ososkov AIS-GRID 2015 Data storage and processing scheme of Tier0-Tier1 level 38 DQ on this scheme denotes not only DAQ of the corresponding experiment, but includes also the means of communications and buffer cleaning. (AN). Initial information to start simulation are parameters of setup ofsetup of designed hardware designed hardware data flow,data flow, job streamjob stream their characteristics are taken from Real data of CMS Tier1 monitoring and TDR DAQ МPD

39 Simulation of T0/T1 1 Reminder: The simulation program is to be combined with a real monitoring system through a special database (DB), which intention is just to input of model parameters and output of simulation results Web-portal is needed to communicate with DB assigning concrete simulation parameters and storing results in DB G.Ososkov AIS-GRID Database design Database contains the description of the grid structure, each of its nodes, links between nodes, running jobs information, execution time, the monitoring results of the various subsystems of the grid and the simulation results. Database main tables Experiments contains information about the experiments;Experiments contains information about the experiments; Simulation_Parameters describes starts (runs) simulation program;Simulation_Parameters describes starts (runs) simulation program; Configurations contains a description of the simulation configuration;Configurations contains a description of the simulation configuration; Jobswaiting contains a description of a job flow (the model of input data);Jobswaiting contains a description of a job flow (the model of input data); Results program results.Results program results. Four types of jobs are generated 1. Data acquisition (DQ) – simulated raw data to be stored 2.Monte-Carlo (MC) – do not need input data 3. Express analysis (EA) – jobs use recently obtained files 4. Reconstruction processing (PR) – jobs consume the most of resources of resources

40 Simulation of T0/T1 2 Web-portal functions Interaction with the database. Present current model structure and generated workflow description. Set new workflow with different parameters (number of DQ, MC, EA, PR jobs) generation. Simulation results representation (graphics, diagrams). G.Ososkov AIS-GRID Simulation algorithm is designed that at the initial time all buffers are empty, the processor is not loaded and data are not transferred. Therefore the initial transition process must be excluded from the analysis. It also happens when the current job flow stops. The result of the simulation program is a sequence of records in the database, which reflects all the events occurring at the system. Snapshot of SyMSim web-portalt

41 Examples of simulation results 1 Fig.1. Disk available space (in terabytes) G.Ososkov AIS-GRID Example 1 What buffer size is needed to store input files on tapes without losses t=system time TB Results in fig.1 show that due to clever buffer cleaning the buffer should not be too big, so we can place it in RAM operational memory Zigzag shape of this curve is due to regular buffer cleaning. The sharp slump in the middle is caused by end-of- tape delay

42 Examples of simulation results 2 42 G.Ososkov AIS-GRID Example 2. Probability of the system overloading due to the disk space lack Load on sw6 network node Fig.2. the load in MB/sec to disk of sw6 network node Two shown and many other results of simulations are very important on the design stage of the NICA project because they give us estimations of the computing infrastructure (structure of robotized tape library, disk storage, CPU numbers, network capacity) needed for reliable storing and processing experimental data. MB/sec

43 43 Заключение Data Mining Data Analysis Взаимо- проникновение, взаимо-обмен методами TMVA - Toolkit for Multivariate Data Analysis ClusteringWWW Big Data 4-я парадигма: интенсивная обработка, распараллеливание, WWW-хранение и обмен Нет теории Знания - из самих данных. Методы корреляции,кластеризации, нечеткой логики, нейросетей нейросетей - - Надежная физическая теория - Детальные моделирующие программы - ROOT: Cluster analysis Hough transform Kalman filter Neural networks Cellular automata Wavelet analysis Математика, теория вероятностей и статистика, вычислительные методы, теоретическое программирование G.Ososkov AIS-GRID 2015

44 44 Final remarks Кто будет осуществлять эти грандиозные проекты компьютинга в ЦЕРНе и ОИЯИ в наступившую в эпоху Больших Данных? -Новые планы нереализуемы без участия талатливой молодежи. талатливой молодежи. Составляющие успеха: Глубокие знания Умение их применить на практике Энтузиазм + здоровое честолюбие (вера в себя) Деньги и толковые руководители

45 45 Thank you for the attention! G.Ososkov AIS-GRID 2015

46 46 Backup slides

47 1. Large increase of CPU and WLCG resources Большие данные = больше CPU (по стоимости на 15% в год) рост дискового пространства (на 15%) рост роботизированных библиотек массового хранения (на 15%) 47 цифры касаются Т0 в ЦЕРНе и Т1-Т2 в странах, входящих в WLCG Важный ньюанс: Закон Мура: экспоненциальный рост числа транзисторов по годам = соответствующий рост числа производимых CPU, однако скорость их работы сдерживается из-за эффекта «тепловой смерти». Поэтому для увеличения производительности вычислительных процессоров потребуются вычислители с большим числом ядер для введения параллелизма и/или применение новых графических GPU процессоров Вы слышали о необыкновенных вычислительных мощностях квантовых компьютеров, но пока это дело будущего После 2014 года более 15% данных LHC обрабатываются в российских центрах WLCG. G.Ososkov AIS-GRID 2015

48 2. Intellectual tools for dynamic data storage 1 Терабайты данных в секунду, производимые в экспериментах ФВЭ и ЯФ, требуют либо сложнейших многоуровневых триггерных процедур или сверхбыстрой параллельной обработки данных для сжатия сырых данных в миллионы раз. 48 Итог – 0.5 экзобайт данных в год, которые требовалось хранить в специальных роботизированных ленточных хранилищах, т.к. копии этих данных подлежат передаче в сотни физических центров 36 стран мира для более тщательного анализа. Для архивирования, изготовления и передачи копий разработаны сложные роботизированные хранилища ленточных картриджей, каждый из которых вмещает по 6.25 терабайт Итог – 0.5 экзобайт данных в год, которые требовалось хранить в специальных роботизированных ленточных хранилищах, т.к. копии этих данных подлежат передаче в сотни физических центров 36 стран мира для более тщательного анализа. Для архивирования, изготовления и передачи копий разработаны сложные роботизированные хранилища ленточных картриджей, каждый из которых вмещает по 6.25 терабайт G.Ososkov AIS-GRID 2015

49 Intellectual tools for dynamic data storage 2. Одной из ключевых проблем в такой системе управления распределением данных является сбалансированный процесс копирования востребованных (горячих) и стирания устаревших (холодных) записей. Проект ATLAS Distributed Data Management - пример автоматической организации такого процесса, выполняющего копирование, доступ, стирание и весь учет оборота данных эксперимента ATLAS в более, чем 120 грид-сайтах. Разработан специальный сервис учета распространения данных (data popularity service) для принятия решений о необходимости увеличения или уменьшения числа копий или полного стирании файла с данными, как вышедшего из употребления. 49 В ЛИТ ОИЯИ разработана и установлена программа ATLAS Deletion Service DQ2, которая ежедневно находит и стирает 2-2,5 миллиона файлов, освобождая до 500 терабайт (порядка 300 к файлов в час). G.Ososkov AIS-GRID 2015