Содержание к диссертации
Введение
ГЛАВА 1. Организация памяти с параллельным доступом 20
1.1. Принципы организации памяти с параллельным доступом 21
1.2. Некоторые перестановки и их свойства 27
1.3. Адресация данных 32
1.4. Параллельный доступ к сегментам многомерных массивов 37
1.5. Выводы 40
ГЛАВА 2. Параллельный анализ динамических образов 43
2.1. Основные цели и принципы построения системы 43
2.2. Некоторые отображения и их свойства 47
2.3. Адресация данных и стробирование 50
2.4. Взаимодействие процессоров с памятью 58
2.5 Процессорные элементы 61
2.6. Отслеживание протяженных объектов 64
2.7. Выводы 71
ГЛАВА 3. Распараллеливание PIC-метода 73
.3.1. Бесстолкновительная модель частиц в ячейках 73
.3.2. Отображение алгоритма на систему с коммутатором 76
3.3. Отображение PIC-метода на гиперкуб 87
3.4. Отображение РІС-метода, на гибридную вычислительную систему 107
3.5. Распараллеливание задачи о взаимодействии потоков плазмы 122
3.6. Выводы 140
ГЛАВА 4. Обработка данных радиоактивного каротажа 141
4.1. Анализ энергетических спектров 141
4.2. Обработка временных спектров и вычисление чистых спектров 146
4.3. Алгоритмы для расчёта нефтенасыщенности методом "Кросс-плот" 155
4.4. Расчёт по методу Дельта С/О 170
4.5. Кластеризация 182
4.6. Выводы 186
ГЛАВА 5. О задачах компьютерной лингвистики 189
5.1. Основные задачи 189
5.2. Программная система Link Grammar Parser 192
5.3. Алгоритмы отождествления предложений 198
5.4. Конструкции языка REFAL и его применение 212
5.5. Определение тем текстов 220
5.6. Результаты тестирования поисковой системы 239
5.7. Выводы 245
Заключение 247
Список литературы
- Параллельный доступ к сегментам многомерных массивов
- Адресация данных и стробирование
- Отображение РІС-метода, на гибридную вычислительную систему
- Алгоритмы для расчёта нефтенасыщенности методом "Кросс-плот"
Введение к работе
Актуальность проблемы
В перечень современных трендов компьютерных технологий входят: специализированные многопроцессорные системы, высокопроизводительные вычисления на суперкомпьютерах, распределенные вычислительные системы, облачные технологии, обработка изображений и сигналов, автоматический анализ текстов на естественном языке, алгоритмы поиска информации в сети и обработки данных из социальных сетей и др. Во всех этих областях приходится иметь дело с многомерными и неоднородными данными, которые необходимо определенными способами организовывать, хранить и обрабатывать, в том числе, на параллельных вычислительных системах.
При этом возникает необходимость в теоретических исследованиях, с помощью которых можно было бы обосновать новые методы организации памяти с параллельным доступом к информации, предлагать новые архитектуры вычислительных систем, методы отображения алгоритмов на различные архитектуры, произвести оценки соответствующих коэффициентов ускорения и др. В основном, такого рода исследования базируются на комбинаторных методах и оценках сложности алгоритмов, хотя, безусловно, необходимо использование знаний из конкретных предметных областей, к которым алгоритмы относятся.
Отметим, что обычно, разрабатываемые подходы являются достаточно универсальными, т.е. они применимы при создании специализированной аппаратуры, как на микро, так и на макро уровне, при реализации программных систем на имеющейся аппаратуре, в том числе, на суперкомпьютерах, в ряде случаев могут быть использованы при распределенной обработке информации, в том числе, в рамках облачной концепции.
В диссертации рассматривается ряд актуальных задач: 1) организация компьютерной памяти, с параллельным доступом к сегментам, содержащимся внутри многомерных массивов, что является важным для вычислительной математики, обработки изображений и сигналов; 2) архитектура вычислительных систем для отслеживания множества подвижных точечных объектов в параллельном режиме; 3) обработка сигналов, получаемых в процессе радиоактивного каротажа нефтяных скважин; 4) лингвистические алгоритмы, а именно, методы определения близости предложений на естественном языке, определения релевантности текста поисковому запросу и определения тем текстов
Тематика исследований соответствует паспорту специальности 05.13.17 -Теоретические основы информатики, пункты: 2, 3, 5, 9, 12.
Цель работы
Цель работы - разработка методов, позволяющих эффективно анализировать и использовать многомерные и неоднородные данные в различных приложениях: вычислительная математика, обработка изображений и сигналов, компьютерная лингвистика, в том числе, на параллельных вычислительных системах.
Для достижения поставленной цели в работе было необходимо было решить следующие задачи:
разработать новые методы организации памяти с параллельным доступам к широкому классу сегментов, содержащихся внутри многомерных массивов;
предложить архитектуру вычислительной системы для отслеживания множества подвижных точечных объектов, обладающую высокой степенью параллелизма в работе;
рассмотреть возможности отображения PIC-метода на различные наиболее интересные архитектуры вычислительных систем;
разработать ряд специфических алгоритмов для обработки сигналов, получаемых в процессе радиоактивного каротажа нефтяных скважин;
проанализировать ряд лингвистических алгоритмов, в том числе методы отождествления предложений на естественном языке.
Методы исследования
В основном, применялись комбинаторные методы, используемые в информатике и информационных технологиях, методы из математической логики. Также был привлечен довольно обширный материал из вычислительной математики, обработки изображений и сигналов.
Научная новизна
1. Создано новое научное направление, базирующееся: на формальных математических методах, включая доказательства теорем, позволяющих описывать, обосновывать и анализировать: принципы организации компьютерной памяти, с параллельным доступом к сегментам, содержащимся внутри многомерных массивов; разрабатывать параллельные архитектуры
вычислительных систем, в том числе, для отслеживания множества подвижных точечных объектов; предлагать методы отображения задач вычислительной математики и обработки изображений на различные наиболее важные архитектуры вычислительных систем - на основе коммутатора, гиперкуб, пара «центральный - графический» процессоры; представлять в виде формул, и при соответствующих предположениях, вычислять коэффициенты ускорения.
-
По заказу ОАО "Западно-Сибирская Корпорация Тюменьпромгеофизика" разработан и реализован ряд алгоритмов для обработки сигналов, получаемых в процессе радиоактивного каротажа нефтяных скважин. Создан ряд программных комплексов. Наиболее важный из них «Анализатор спектров» (SpectrumAnalyzer). Он предоставляет широкие возможности для обработки каротажных данных: загрузка, просмотр и обработка исходных амплитудных и временных спектров; расчет различных аналитических параметров; вычисление концентраций естественных радионуклидов; экспорт результатов обработки в формате LAS, применяемом в геофизике. Алгоритмы и программный комплекс используются при эксплуатации нефтяных месторождений и конкурентоспособны с мировыми аналогами. Таким образом, решена прикладная задача важная для народного хозяйства.
-
Проанализирован и обобщен ряд лингвистических алгоритмов, в том числе методы определения близости предложений на естественном языке, определения релевантности текста поисковому запросу и определения тем текстов. Предложенный подход базируется на использовании грамматики связей, построенной на ее основе программной системы Link Grammar Parser и методах математической логики. При этом основными рассматриваемыми структурами данных являются конечные модели (в смысле теории моделей, как раздела математической логики) и частичные отображения между ними, обеспечивающие истинность определенных формул.
Практическая ценность
Результаты первой и второй глав диссертации были получены в процессе работы по теме «Мозаика», которая выполнялась в Институте теоретической и прикладной механики СО РАН совместно с НТО «Феникс», г. Омск для Инсти-
тута физики полупроводников СО РАН. Результаты также были использованы в Институте автоматики и электрометрии СО РАН.
Результаты 3-й главы имеют исследовательский характер, но в целом, они полезны специалистам по вычислительной математике, использующим в своей практике параллельные вычислительные системы.
Результаты 4-й главы получены в процессе работы по заказу ОАО «Западно-Сибирская Корпорация "Тюменьпромгеофизика"». Программный комплекс «Анализатор спектров» (SpectrumAnalyzer) внедрен в Интерпретационном центре ЗСК ТПГ, г. Мегион, Ханты-Мансийский Национальный Округ. Остальные работы были выполнены для заказчиков из Респ. Казахстан, там же внедрены соответствующие программные комплексы.
Результаты 5-й главы применены в системе интеллектуального поиска, реализованного в ИСИ СО РАН А.А. Перфильевым. Частично использовались А.В. Проскуряковым в работах по определению спам сообщений и рассылыци-ков спама. Работа выполнялась по заказу. Предполагается использовать результаты данной главы в программном комплексе анализа данных из социальных сетей также разработанным в ИСИ СО РАН, (комплекс реализован А.В. Проскуряковым). В настоящее время также ведутся работы применительно к тюркским языкам.
Апробация работы
Результаты работы докладывались на следующих конференциях и семинарах: Совещание по системам аналит. вычислений на ЭВМ, Дубна, 1982; Школа-семинар соц. стран "Вычислительная аэрогидромеханика", Москва-Самарканд, 1985; Междунар. конф. по обработке изображений и дистанционным исследованиям, Новосибирск, 1990; Intern, conf. "Visual Analysis and Interface", Novosibirsk, 1991; Intern, conf. on the Methods of Aerophysical Research (ICMAR'96), Novosibirsk, 1996; Междунар. симп. "Математические модели и численные методы механики сплошной среды", Новосибирск, 1996; XVI Междунар. школа-семинар по численным методам механики вязкой жидкости, Новосибирск, 1998; IV Сибирский конгресс по прикладной и индустриальной математике (ИНПРИМ'2000), Новосибирск, 2000; Междунар. конф. "Портативные генераторы нейтронов и технологии на их основе", Москва 2004; 15th Intern, conf. on Computer Graphics and Applications (GraphiCon'05), 2005; V Российско-германская школа по параллельным вычислениям на высокопроизводительных вычислительных системах. Семинар "Распределенные и высоко-
производительные вычисления", Новосибирск, 2008; Росс, научно-техн. конф. "Информатика и проблемы телекоммуникаций", Новосибирск, 2011; Intern, conf. "Advanced Mathematics, Computations and Applications" (AMCA2014), Novosibirsk 2014; V, VI, VII, VIII Международные конференции памяти академика А.П. Ершова "Перспективы систем информатики", рабочий семинар "Наукоемкое программное обеспечение", Новосибирск, 2003, 2006, 2009, 2011; Working Seminar of Univ. of Paris-Sud (Univ. of Paris XI), Lab. of Information Science and Technology, Paris, France, 2010; 3rd Global Congress on Intelligent Systems (GCIS'2012) and 3rd Word Congress on Software Engineering (WCSE2012), Wuhan Univ. of Technology; Wuhan, China, 2012; Intern. Workshop on Enterprise Information Systems in Cloud Computing Envirionment, Beijing University of Posts and Telecommunications; Beijing, China, 2012; Working Seminar of State Key Laboratory Automation for Process Industries, Northeastern Univ. Shenyang, Shenyang, Liaoning, China, 2012; Working Seminar of Hebei Univ. of Science and Technology, School of Economics and Management, Dep. of Information Management, Shijiazhuang, Hebei, China, 2012; XIII Conf. of Intelligent Text Processing and Computational Linguistics (CICLing), Indian Inst, of Technology, Delhi, India, 2012.
Результаты диссертации также были представлены в виде докладов и/или стендов на научно-технических выставках: Российская научно-техн. выставка в Индии, Expo Centre EXPO XXI, Инновационная зона Нойда, Индия, 2008; Российская научно-техн. выставка в США, Exhibition Center McCormick Place, Чикаго, CIIIA, 2009; Российская научно-техн. выставка во Франции, Выставочный центр «Гранд Пале», Париж, Франция, 2010; Вторая междунар. инновационная ярмарка, Гуанчжоу, Китай, 2012; Неделя междунар. научно-техн. сотрудничества в 2013 году, Дунгуань, Китай, 2013.
Публикации
По теме диссертации опубликовано более 100 работ. Из них 5 монографий в соавторстве, 16 из списка ВАК, Scopus и Web of Science
Структура и объем работы
Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы и одного приложения. Объем диссертации - 279 страниц. Список литературы содержит 221 наименование. Работа включает 69 рисунков и 8 таблиц.
Параллельный доступ к сегментам многомерных массивов
Таким образом, теорема 3.1 указывает способ адресации данных, позволяющий посредством предложенных выше конструкций памяти, осуществлять параллельный доступ к сечениям, выделяемым в исходном массиве фиксацией одной из координат.
Из теоремы 3.2 получаем возможность доступа к любому блоку размером гх хг2 х...хгк. Хотя при втором способе адресации доступны только те сечения, которые получаются фиксацией первой координаты.
Если воспользоваться теоремой 3.3, то вновь получаем возможность доступа ко всем сечениям, доступным в первом случае. Кроме этого возможен доступ к большому набору параллелепипедов, имеющих размер n kxrxxr2x...xrk, хотя не ко всем. Заметим, что когда к = 2 имеем п к =т1. Нетрудно понять, каков этот набор. В любом слое, определенном неравенствами sn k ix (s + i)n k,s 0, доступен любой блок, указанного вида.
Последняя теорема показывает, что обеспечить доступ к большому набору сечений и блоков одновременно может оказаться невозможным. Условие СЗ обозначает, что массив достаточно большой..
Приведенные выше теоремы указывают, каким образом следует поступать с одним массивом. В случае, когда имеется несколько массивов, размещение их в памяти обеспечивается варьированием отображений є0,є1 и разбиением некоторых массивов на части более удобные (на два или несколько подмассивов).
В частности, с их помощью легко построить необходимый набор є\,...,є,є\,...,є для последовательности массивов A1(n11,...,n1ki\...,Am(n,...,nJ таких, что 6У =Y\n) = Const или таких, что ві ./=2 степени числа 2. Произвольный случай можно свести к последнему. Мы здесь опускаем также вопрос, каким образом параллельно вычисляются адреса и номера модулей и вопрос о том, насколько естественны условия СО-СЗ. Отметим лишь, что СО, как правило, несущественно. 1.4. Параллельный доступ к сегментам многомерных массивов
В данной главе дано формальное математическое описание организации памяти, предназначенной для хранения произвольного набора конечномерных массивов. Естественно, что суммарный объем массивов, не должен превосходить общий объем памяти. В рассмотренной модели памяти возможно осуществление параллельного доступа к сечениям, выделяемым в массивах фиксацией одной из координат, и к большому набору многомерных параллелепипедов, являющихся подмассивами той же размерности в исходных массивах.
Базовой идеей является использование перестановок данных в многомерных массивах таких, что данные «хорошо расположены». В действительности, пространство памяти является двумерным. По одной координате располагаются модули памяти, по другой - адреса. В итоге используется композиция перестановки и вложения многомерного массива в двумерный.
Хорошее расположение данных означает, что элементы сегментов, которые нас интересуют (например, сечения иили параллелепипеды) лежат в разных модулях памяти. Именно это обеспечивает возможность параллельного доступа к их элементам. Необходимо также помнить о том, что функции, указывающие номер модуля и адрес, где расположен конкретный элемент массива, должны быть достаточно простыми в сложностном пане.
Теоремы 1.1 - 1.3 указывают способы расположения данных, позволяющие посредством предложенных выше конструкций памяти, осуществлять параллельный доступ к различным множествам сечений, выделяемым в исходном массиве фиксацией одной из координат и множествам блоков. Теорема 1.4 показывает, что обеспечить доступ к большому набору сечений и блоков одновременно может оказаться невозможным.
Организованная таким образом память в некотором смысле напоминает жидкий кристалл, который способен находиться в различных состояниях. Каждое из распределений данных обеспечивает доступ к определенного вида информации.
Относительно системы управления памятью можно сказать следующее. Всё достаточно очевидно для системы на основе коммутатора. Для случая использования корректора ситуация менее очевидна. Для больших размерностей алгоритмы коррекции усложняются. Для этих случаев часто не ясно, как коррекцию можно осуществить в параллельном режиме. Даже для двумерного случая оборудование корректора может быть довольно громоздким. Поэтому схемы с корректором на практике используются довольно редко.
Адресация данных и стробирование
Ранее отмечалось, что предложенные средства могут быть использованы для отслеживания не только точечных, но и протяженных объектов. Идея состоит в том, что изображение протяженного объекта можно разметить точками на контуре или даже внутри и далее отслеживать движение этих точек.
Опишем теперь, каким образом можно отслеживать движение протяженных объектов. Допустим, что имеется такой объект. Можно определенные места на его контуре и внутри пометить точками. Это может быть сделано как программным путем, так и пользователем с помощью "мыши", светового пера и т.д. Дальше отслеживаем за движением данных точек. Процессоры при этом могут обмениваться между собой информацией об их координатах. Это позволяет наблюдать для отдельных, интересующих нас точек, меняются ли между ними расстояние, углы и т.д. Изменение этих величин свидетельствует об изменении формы объекта. Беря большее или меньшее число точек можно следить за объектом с большей или меньшей детальностью. Можно анализировать также окрестности вблизи некоторых точек, для большей надежности. Так как мы все равно работаем с окнами. В частности, если объект ограничен контуром, то можно настолько часто расположить на нем точки, что окна полностью покроют этот контур. Интересно, что при таком подходе к обработке протяженных объектов система не требует никаких изменений.
Разбивая множество точек, осуществляющих разметку, на подмножества по тем или иным критериям, мы по сути дела можем осуществлять сегментацию изображения. Используя большее или меньшее число точек для разметки, мы осуществляем более или менее детальный анализ изображения, а также учет его геометрии.
Отметим, что такой подход к проблеме сегментации не является типичным, например, в случае, если образ размыт, он, по-видимому, может оказаться неэффективным. Размытые образы возникают, например, в задаче локализации особенностей течений в газовой динамике. Но нас в большей мере интересуют образы, содержащие объекты искусственного происхождения.
Задача идентификации объекта может быть поставлена как задача взаимодействия с базой данных содержащей набор эталонных образов. Переходим теперь к формальному изложению методов отслеживания объектов. Отметим также, что данные исследования носят, в некотором смысле, предварительный характер и, очевидно, что возможны другие подходы. Как и раньше, предполагаем, что имеется квадратная мозаика. Каждый элемент мозаики представляет собой квадрат и характеризуется парой координат (i,j), \ i,j М. Считаем, что мы имеем полутоновое изображение, заданное с помощью функции яркости S:M2 — R. При этом R - вещественные числа. На первом этапе производится преобразование полутонового изображения в логическую матрицу Т = (/..). информативными, т.е. их необходимо выделить при разметке объекта. Условие Nc(i,j) = 2 ничего не дает. Здесь необходимы другие критерии. Если контур имеет излом в данной точке, то ее целесообразно выделить. В противном случае это делать нежелательно.
Естественным образом нумеруются направления движения: от данной точки по направлению к элементам, расположенным на окружности с центром в этой точке. Поэтому, если даны два соседних 8-связных элемента (hJi) {h J 2) таких, что (ix -i2)2 +0\ - Л)2 -2, то назовем направлением движения от первого элемента ко второму номер вектора, соединяющего эти элементы.
Для разметки контура используем только те элементы, в которых меняется направление движения. Нетрудно видеть, что если мы имеем, например, прямоугольник, стороны которого параллельны сторонам мозаики, то после применения алгоритма останутся всего четыре угловых точки. Однако для геометрически сложных кривых может оказаться слишком много точек, в которых меняется направление. В этом случае ряд точек может быть отсеян исходя из метрических критериев.
Аналогично, используя метод взвешивания точек можно закодировать структуру объекта. Например, более крупным или более важным деталям приписать одни веса, более мелким или менее важным - другие. Выделяя множество точек, веса которых лежат в определенных интервалах, можно произвести декомпозицию объекта на части. При этом если рассматриваемые интервалы могут быть соединены отношениями включения, то соответствующую взаимосвязь можно получить для фрагментов образа. r3 r Рис. 2.10. Пример декомпозиции объекта. выделение фрагментов с помощью весов. Описанный алгоритм может быть использован при создании базы данных изображений. В идеальном случае изображения должны вводиться с помощью соответствующей аппаратуры для оцифровки изображений. Разметка изображения и аппроксимация их в базе данных должны производиться автоматически.
Нетрудно видеть, что объекты рассматриваемой базы данных представляют собой взвешенные графы, а ее структура может быть реализована в рамках реляционного подхода [25]. При наличии множества процессоров они могут работать параллельно. Теперь коротко о задаче идентификации. Допустим, база данных уже имеется. Получено новое изображение, которое можно разметить по описанному алгоритму. То, что получилось, может отличаться оттого, что имеется в базе данных с точностью до масштаба поворота, также расположения точек разметки. В настоящее время в литературе предложено много методов определения ориентации, приведения к одному масштабу и проверки совпадения с эталоном [26]. Конечно, эти методы для различных классов изображений имеют различную эффективность.
В данной главе предложена архитектура вычислительной системы для отслеживания множества подвижных точечных объектов, обладающая высокой степенью параллелизма в работе;
Световой сигнал воспринимается фотоприемной матрицей, функционирующей по принципу ПЗС - прибора с зарядовой связью. Размерность матрицы матрицы достаточно большая. На том же кристалле расположена некоторая схема. Первая ее цель состоит в том, чтобы сузить информационный поток. Вторя цель - осуществить перестановку данных в соответствии с некоторым алгоритмом. Далее информация об некоторых множествах точках (пикселях) одновременно в параллельном режиме перекачивается в несколько модулей памяти и располагается там некоторым нестандартным образом. В памяти места должно быть достаточно, чтобы за несколько этапов можно перекачать всю матрицу, т.е. всё изображение. При этом возникает отображение квадратного массива данных размерности в прямоугольный массив пространства памяти.
Отображение конструируется в соответствии с идеями, изложенными в предыдущей главе. А именно, обеспечивается, чтобы для любого квадрата небольшой размерности п х п, содержащегося в исходном массиве, оказалось бы, чтобы его элементы лежали в различных модулях памяти. Они могут располагаться, вообще говоря, по различным адресам. Но это малосущественно.
Важно то, что элементы расположены в различных модулях, и это позволяет параллельно генерировать все необходимые адреса и все элементы квадрата одновременно считать из памяти отправить на один или несколько процессоров для обработки. То есть обработка производится окнами размера пхп,ъ параллельном режиме. Любое окно размера пхп доступно, и можно окнами следовать за «целями».
Отображение РІС-метода, на гибридную вычислительную систему
Распределение частиц по процессорам считаем фиксированным, например: нулевой процессор обрабатывает частицы с номерами --- первый - с номерами + -/ и т.д. Обозначим через ЖУ) множество номеров частиц, которые рассчитывает -й процессор. Вложение сети в гиперкуб Для простоты посчитаем, что каждый процессор отвечает в точности за одну ячейку. Пусть у нас есть сетка , где 2п - количество ячеек по оси X, а 2т - по оси Y. Необходимо отобразить ячейки сетки на процессоры в мультикомпьютере с топологией гиперкуба таким образом, чтобы если 2 ячейки в сетке были бы соседями по оси X или Y, то и процессоры, отвечающие за эти ячейки, были бы соседями. Алгоритм вложения описан ниже и показан на методическом примере (рис. 3.7). Эта задача аналогична задаче вложения сетки в гиперкуб с условием того, что соседние узлы на сетке должны вкладываться в соседние узлы в гиперкубе. Для решения этой задачи [36] воспользуемся кодом Грея -перенумеруем координаты узлов в сетке по X и Y и зададим функцию отображения Fg(x, у) = G(x, Nx)G(y, Ny). Nx и Ny - количество разрядов по соответствующим координатам. Операция - означает конкатенацию кодов Грея.
Таким образом, мы отобразили ячейки двумерной сети на процессоры в гиперкубическом мультикомпьютере. Если же количество ячеек в сетке больше чем процессоров, то мы просто имеем более крупное разбиение сетки и задача сводится к вложению сетки меньшего размера в гиперкуб. Этот подход можно применить для отображения сетей и торов любой размерности на гиперкуб.
Одной из главных задач при распараллеливании алгоритмов является задача нахождения эффективного механизма обмена информацией между процессорами. В связи с этим отметим работы [34-35], в которых рассматривался вопрос о решении системы линейных уравнений с трехдиагональной матрицей и о реализации задач обработки изображений на гиперкубе. В РІС - методе можно выделить два класса коммуникаций - это обмен информацией между соседними процессорами и обмен информацией «каждый с каждым». Так как при коммуникации между процессорами, находящимися на расстоянии больше 1, прямой доступ к памяти соседнего процессора не возможен, то используем механизм обмена сообщениями. Для унификации механизма коммуникаций, используем обмен сообщениями и для связи между соседними узлами.
Время этапа коммуникаций - величина, зависящая от таких факторов как: размер сообщений, ширина канала. В [6] упоминается, что время на передачу числа с одного процессора на соседний на порядок-два больше времени выполнения арифметической операции. С условием того, что количество сообщений, которое необходимо передать за время выполнения шага РІС-метода пропорционально количеству процессоров, время коммуникации существенно влияет на время работы алгоритма в целом. Возникает задача минимизировать это время. В дальнейших рассуждениях в этой главе будем исходить из того, что ширина канала между соседними процессорами позволяет передать одно сообщение в одно направление за единицу времени.
В РІС-методе есть этапы, когда каждому процессору необходимо знать некоторые значения в ячейках соседствующие с ячейками, за которые он отвечает. Механизм обмена: Пусть Т - процессор в мультикомпьютере отвечающий за некоторую группу ячеек Л, a Tnorth, Twest, Tsouth, Teast - соседние процессоры, отвечающие группы клеток на сетке с севера, запада, юга и востока от Л. Если процессор отвечает за граничную группу клеток, то каких-либо соседних процессоров может и не быть. На каждом первом шаге все процессоры отправляют сообщения на соседние процессоры Tnorth. Если такого процессора нет, то пропускают шаг. На последующих шагах сообщения отправляются на процессоры Twest, Tsouth, і east При таком алгоритме, на каждом шаге каналы связи между процессорами на каждом шаге будут загружены не более чем одним сообщением в одном направлении.
Существует несколько известных механизмов рассылки сообщений от каждого процессора к каждому на мультикомпьютере с топологией гиперкуба. Это такие алгоритмы, как алгоритм обобщенной множественной рассылки (total exchange) и метод покоординатной маршрутизации. Однако они имеют существенный недостаток: при одновременной передаче сообщений всеми процессорами нагрузка на каналы обмена не равномерная, вследствие чего, время коммуникации может существенно увеличится. Попробуем улучшить алгоритм обмена. Для этого введем новое понятие.
Смежные вершины к вершине х, определим как вершины, находящиеся на расстоянии 1 от вершины х. Для вершины х в гиперкубе, порядок приоритета смежных узлов зададим следующим образом: пусть Gr(X) - код Грея сдвинутый относительно вершины X. (рис. 3.8). Порядок узлов в Gr(X) смежных с вершиной х и будет порядком приоритета смежных узлов для вершины х. Для краткости, вместо «Порядок приоритета смежных узлов относительно х» будем говорить ППСУ от х.
Как можно заметить, сообщение идет по наикратчайшему пути. Причем при одинаковых размерах сообщений нагрузка на каналы распределяется равномерно, то есть на каждом шаге каждый канал загружен не более чем одним сообщением в одном направлении. К сожалению, этому факту четкого доказательства не было найдено, однако были программно обсчитаны гиперкубы размерности 12, на них это свойство выполняется. Также надо заметить, что этот алгоритм не работает для соседних узлов.
Для коммуникаций с соседними узлами обычно используется покоординатная отправка сообщений. То есть сначала все узлы отправляют сообщения по первой координате, потом по второй и так далее. По-видимому, это не самый эффективный способ. Существует обход гиперкуба с использованием кода Грея (рис. 3.9).
Алгоритмы для расчёта нефтенасыщенности методом "Кросс-плот"
Область решения имеет форму параллелепипеда. В ней введена, декартова система координат (x,y,z). Вся область разбита на одинаковые ячейки такой же формы с размерами hx, h hz вдоль соответствующих направлений. Для повышения точности аппроксимации электромагнитных полей внутри ячейки используется их представление в сдвинутых сетках, показанное на рис. 3.33. Частицы, моделирующие плазму, располагаются внутри ячеек в соответствии с необходимой плотностью. Каждая частица имеет свою скорость, которая изменяется под действием электрического и магнитного полей. Друг с другом частицы не взаимодействуют.
Здесь нижние индексы /, 7 , к показывают положение соответствующей величины на пространственной сетке в направлениях (д:,у,2)соответственно. Верхний индекс т указывает шаг по времени, hx, hy, hz - пространственные шаги по осям х, у , z.
Этап 2. По найденным значениям магнитных полей и значениям электрического поля на предыдущем слое вычисляются новые скорости частиц
Нижний индекс j указывает номер частицы. Значения напряженностей электрического и магнитного полей определяются для каждой частицы отдельно путем интерполяции по восьми значениям в ближайших к частице узлах пространственной сетки. Поскольку все сеточные величины заданы на сдвинутых относительно друг друга сетках, то интерполирующие множители для каждой величины различны. Формулы для определения скоростей записаны неявно, в виде системы линейных алгебраических уравнений, которая решается аналитически, что дает явные выражения для компонент скорости на новом временном слое.
Из этой формулы видно, что функция R(X) отлична от нуля только на интервале длиной 2/z. Поэтому суммирование ведется только по частицам, расстояние которых до узла сетки не превышает шага h.
Итак, исходная постановка задачи в семимерном пространстве путем использования метода частиц свелась к более сложной постановке, но в трехмерном пространстве. Решение уравнения Власова заменилось решением уравнений движения для большого количества частиц.
Частицы и поля, описывающие физическую часть задачи, в алгоритме представляются двумя вычисляемыми объектами - множеством частиц и равномерной эйлеровой сеткой (узлами сетки являются вершины ячеек, на которые делится пространство моделирования). Каждая частица находится внутри определенной ячейки сетки.
Число частиц M))N. Сформулируем требования на архитектуру ЭВМ, которая могла бы быть пригодна для реализации РІС-метода.
Считаем, что каждой ячейке сетки соответствует процессор, который вычисляет напряженность электрического поля и другие параметры, связанные с данной ячейкой. Предполагаем, что число процессоров равно К При вычислении некоторых величин требуются данные из соседних ячеек. Для простоты считаем, что М делится на К и R = M/K. Каждый процессор будет рассчитывать данные в точности для R частиц. Распределение частиц по процессорам считаем фиксированным, например: процессор с номером ноль обрабатывает частицы с номерами . второй -с номерами R + \,...2R и т.д. Обозначим ж{і) - множество номеров частиц, которые рассчитывает / - й процессор.
Обмен данными между процессорами производится через коммутатор, структуру которого не уточняем, но считаем, что если задана функция а: {О,...Д-і}- {0,...JC-\\ то коммутатор способен обеспечить связь всех процессоров Пд. с процессорами П ч, (0 к К) одновременно в параллельном режиме, после чего произойдет передача данных. Структура алгоритма такова, что конфликты при записи исключены. Несущественно, происходят ли обмены между процессорами непосредственно или через общую память. Архитектура ЭВМ, удовлетворяющая перечисленным выше условиям, показана на рис. 3.1.
При вычислении некоторых величин требуются данные из соседних ячеек, т.е. фактически из других процессоров.
Трижды повторив подобные действия, все процессоры получат все необходимые для вычисления величины. Опишем процесс обработки данных, касающихся частиц, в параллельном режиме. Все процессоры одновременно производят сортировку частиц и предварительные вычисления. Каждый процессор П разбивает множество ттк на дизъюнктивные компоненты як =u =l7rv(k), где 7iv(k) - множество номеров частиц /ЛЄ7г(к), таких, что частица с номером // находится в ячейке, имеющей номер v.
Кроме того, коэффициент ускорения зависит также от констант $, (3, /, которые определяются сложностью вычислений, возникающих при расчете одной ячейки или одной частицы. В конечном итоге, эта сложность определяется сложностью соответствующих формул.
Отметим, что при увеличении (X, /?, у эффективность вычислений, как правило, возрастает. С другой стороны, для большинства задач важных на практике, значения ОС, /3, у небольшие.
Так же, как и в предыдущих задачах, можно выделить несколько возможных направлений дальнейших исследований. Интересно было бы получить аналогичные оценки для других архитектур ЭВМ, например матричной и гиперкуба. Большое практическое значение имеет исследование ситуации, когда данные, соответствующие частицам, не входят в суммарную локальную память процессоров. В этом случае приходится производить непрерывные обмены данными с внешними носителями. Целесообразно развить исследования, учитывающие статистику распределения частиц. В этом случае следует говорить о математическом ожидании времени исполнения алгоритма. При этом могут быть использованы различные методы теории информации, теории массового обслуживании, теории случайных блужданий и т.д. Статистическая информация задается априорно или накапливается в процессе расчета. Такой подход может оказаться плодотворным для следующих случаев: