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

Список сокращений.

ВВЕДЕНИЕ

ГЛАВА 1. Анализ основных принципов информационного обмена внутри вычислительных систем

1.1 Построение современных высокопроизводительных вычислительных систем. Кластерный подход

1.2 Реализация коммуникационной среды для построения ВС кластерного типа

1.3 Построение ВС на основе стандартного интерфейса SCI

1.4 Особенности построения ВС на основе коммуникационной среды MYRINET

1.5 Fast Ethernet - сеть связи ВМ систем кластерного типа

ВЫВОДЫ

ГЛАВА 2. Разработка методов высокоскоростного внутрикластерного обмена

2.1 Структура ВС кластерного типа.

2.2 Особенности возможного использования для выбранной кластерной структуры

2.3 Организация обмена по протоколу

2.4 Организация обмена по протоколу

2.5 Определение времени коммутации и скорости передачи информации в различных режимах обмена

2.6 Сравнительный анализ эффективности использования методов высокоскоростного внутрикластерного обмена

2.7 Оценка качества функционирования системы . 103 ВЫВОДЫ.

ГЛАВА 3. Реализация методов высокоскоростного внутрикластерного обмена.

3.1 Описание варианта функциональной схемы адаптера PCI.

3.2 Описание варианта построения коммутатора и его функциональной схемы.

3.3 Адаптеры PCI. Алгоритм работы.

3.4 Алгоритм работы адаптера PCI в мультиплексном режиме.

3.5 Алгоритм работы адаптера PCI в псевдомультиплексном режиме.

3.6 Алгоритм работы коммутатора.

ВЫВОДЫ.

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

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

Всё это приводит к применению сложных протоколов обмена внутри ВС, что снижает скорость передач и увеличивает вероятность возникновения конфликтов в коммуникационных средах. При этом в некоторых случаях [1,5] уменьшается вероятность достижения сообщениями адресатов.

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

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

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

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

В то же время для таких систем нет необходимости рассредоточивать^ основные вычислительные средства и иметь широкую единую адресацию узлов.

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

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

За последние несколько лет проблеме исследования и разработки методов межмодульного информационного обмена внутри ВС было посвящено немало работ отечественных и зарубежных специалистов. В трудах этих ученых [1,2,3,5,8,13,16,20] рассматриваются различные аспекты повышения эффективности операций обмена между узлами ВС, предлагаются различные архитектуры систем: массово параллельные, кластерные, симметричные мультипроцессоры, предлагаются специализированные коммуникационные среды для объединения вычислительных узлов в рамках ВС.

Сегодня уже существуют специализированные средства для построения ВС. Например, коммуникационные среды Fast Ethernet [5], SCI фирмы Dolphin Interconnect Solutions [4], MYRINET фирмы MYRICOM [3], Memory Channel фирмы DEC [2] и другие. Каждая из них имеет свои особенности, преимущества и недостатки, которые будут рассмотрены в 1 главе. В настоящее время имеется немало примеров тому, как такие коммуникационные среды используются для построения ВС кластерного типа [9,10,12,13,14]. Однако используемые протоколы обмена достаточно сложны, реализованы программно-аппаратным способом и предусматривают широкую единую адресацию узлов в системе. Для таких ВС характерна малая разрядность передач внутри кластера (например, Шит при использовании Fast Ethernet, 1 байт при использовании

MYRINET). Все эти обстоятельства существенно увеличивают реальные значения времени передачи относительно теоретически возможных и снижают скорости обмена внутри ВС. Кроме того, часто возникающие конфликты при передачах внутри ВС требуют инициирования повторных запусков обмена (например, в однонаправленном кольце SCI возможно до 256 повторных запусков, в Fast Ethernet - до 16) и эффективного решения задачи приоритетности.

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

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

Первая глава работы посвящена анализу получивших наибольшее распространение принципов информационного обмена внутри ВС. Эти принципы лежат в основе протоколов существующих на сегодняшний день коммуникационных сред, которые являются специализированными средствами, предназначенными для построения высокопроизводительных ВС [2,3,4,5,6,7,8].

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

• Разработка методов высокоскоростного внутрикластерного обмена и их теоретическое обоснование.

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

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

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

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

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

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

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

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

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

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

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

• Предложены и реализованы протоколы внутрикластерного обмена, обеспечивающие многорежимный высокоскоростной обмен.

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

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

Диссертационная работа в целом и отдельные её результаты докладывались и обсуждались на шестой международной научно-технической конференции студентов и аспирантов "Радиоэлектроника, электротехника и энергетика" в Московском энергетическом институте (техническом университете) ? 1 - 2 марта 2000 года, на семинарах "Массовые параллельные системы и вычисления" в "Производственной организации Вычислительной техники и средств автоматизации", а также в войсковой части № 11135, 21 - 22 декабря 2000 года, на кафедре Вычислительной техники МИРЭА (ТУ).

Предложенные в работе методы и протоколы внутрикластерного обмена, а также разработанные функциональные схемы и алгоритмы работы адаптеров и коммутатора устройства мультипроцессирования были использованы при реализации ВС кластерного типа в ЗАО "Производственная организация Вычислительной техники и средств автоматизации", а также при проведении НИОКР в войсковой части №11135, что подтверждено соответствующими актами о внедрении.

Материалы, отражающие основное содержание исследований и разработок изложены в 5 научных работах, а также в авторском свидетельстве.

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

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

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

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

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

5. Для каждого протокола предложено несколько методов внутрикластерного обмена.

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

7. Построена вероятностная модель поведения системы.

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

9. Показано, что скорость передачи двойного слова внутри кластера предложенной структуры на порядок выше, чем при

160 использовании самого распространённого на сегодняшний день способа объединения узлов в ВС на базе Ethernet.

10. Разработаны варианты функциональных схем структурных единиц (адаптеров PCI и коммутатора), составляющих внутрикластерную коммуникационную среду.

11.Реализованы следующие режимы обмена:

- мультиплексный режим;

- псевдомультиплексный режим.

12.Разработаны алгоритмы работы адаптеров PCI и коммутатора в предложенных режимах.

13.Результаты проведённых исследований и разработок положены в основу создания компактно сконструированного 16-ти узлового кластера в ЗАО ПО "Вычислительная техника и системы автоматизации".

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

ЗАКЛЮЧЕНИЕ

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

В ходе исследований было установлено, что одна из главных особенностей существующих коммуникационных сред для построения ВС - установка на возможность объединения в систему узлов (например, персональных компьютеров или материнских плат), значительно удалённых друг от друга.

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

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

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

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

Предложенный подход позволил:

- построить компактно конструктивно оформленные кластеры, которые содержат до 16 вычислительных модулей (узлов);

- достичь длин связей между узлами, суммарно не превышающих 0,5 м;

- упростить протоколы внутрикластерного обмена;

- обеспечить полноразрядную передачу, реализованную в печатном монтаже и плоском кабеле;

- обеспечить мультиплексный обмен между узлами, сочетающий одновременность работы по чтению (записи) из (в) PCI и передаче информации от каждого узла к каждому;

- минимизировать время обмена за счёт чисто аппаратной его реализации;

- существенно понизить значение вероятности возникновения конфликтов в коммуникационной среде;

- минимизировать время программной обработки сообщений.

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

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

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

Основной эффект повышения скорости передачи внутри кластера даёт:

- совмещение времён передачи PCI - шины со временем передачи по цепям коммутатора;

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

- параллельная полноразрядная передача;

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

Были предложены два протокола организации обмена внутри кластера для случаев:

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

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

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

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

Соответственно, время коммутации и работы в одном направлении составляет 3 такта (<90 не).

Было показано, что частота передачи одного двойного слова составляет 11 МГц. Соответственно, скорость передачи составляет 433Мбит/с.

Было рассчитано значение скорости передачи в мультиплексном режиме одновременно по всем направлениям, которое составило 3464Мбит/с, что более чем на порядок больше, чем у Ethernet.

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

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

Были разработаны варианты функциональных схем адаптеров PCI и ТЭЗов коммутатора, а также реализованы два из предложенных методов внутрикластерного обмена. Для них разработаны алгоритмы работы адаптеров источника и адресата передаваемой информации. Разработан алгоритм работы коммутатора.

1. Корнеев В.В. Параллельные вычислительные системы. М.: Нолидж, 1999.

2. M.Fillo, R.Gillett. Architecture and Implementation of Memory Channel. DEC. High Performance Technical Computing. April 1997, pp.34 48 .

3. N.Boden, D.Cohen. Myrinet: a Gigabit-per-Second Local Area Network. IEEE Micro. Feb. 1995, pp. 29 -36 .

4. IEEE Computer Society. IEEE Standard for Scalable Coherent Interface (SCI), IEEE Std. 1596 1992, New York, August, 1993.

5. Л. Куин, P. Рассел. Fast Ethernet. Перевод с английского под ред. К. Королькова. Киев, BHV, 1998.

6. Золотов С. Протоколы Internet. М.: BHV, 1998.

7. Т. Паркер. Освой самостоятельно TCP/IP. М.: Бином, 1997.

8. Фролов А.В., Фролов Г.В. Локальные сети персональных компьютеров. Использование протоколов IPX/SPX. М.: Диалог МИФИ, 1993.

9. SUN Microelectronics (http://www.sun.com/microelectronics).10.NCR (http://www.ncr.com)11 .Sequent (http://www.sequent.com)

10. Digital (http://www.digital.com)

11. J.Lindheim. Building a Beowulf System, (http://cesdis.gsfc.nasa. gov/beowulf)

12. Introduction Avalon. (http://www.eklectix.eom/Iwn/980507/a/ avalon.html) 15.Dolphin Interconnect Solutions, Inc. http://www.dolphinics.com. 16.S.Scott. The GigaRing Channel. IEEE Micro Feb. 1996, pp. 27 34.

13. VITESSE Semiconductor Corporation, (http://www.vitesse.com)

14. Data General Corp. (http://www.dg.com)

15. Cypress Semiconductor Corporation.

16. Новиков Ю.В., Карпенко Д.Г. Аппаратура локальных сетей: функции, выбор, разработка. М.: Эком, 1998.

17. Sebring Systems, Inc. (http://www.sebringring.com)

18. TMS 320 C4X User's Guide. Texas Instruments, 1993.

19. Кондрашов А.Ф., Кушнеров Ф.Р. Средства повышения производительности систем, работающих в реальном времени.-Проблемы информатизации №1 - 2, М., 1997.

20. Головкин Б.А. Параллельные вычислительные системы. М., Наука, 1980

21. Поспелов Д.А. Введение в теорию вычислительных систем. М.: Сов. радио, 1972

22. Праневичус Г.И. Модели и методы исследования вычислительных систем. Вильнюс: Мокслас, 1982.

23. Клейнрок Л. Вычислительные системы с очередями: Пер. с англ. М.: Мир, 1979.

24. Клейнрок Л. Теория массового обслуживания: Пер. с англ. М.: Машиностроение, 1979.31 .Мультипроцессорные системы и параллельные вычисления: Пер. с англ./ Под ред. Ф.Г. Энслоу. М.: Мир, 1976.

25. Основы теории вычислительных систем: Учебное пособие/ Под ред. С.А. Майорова. М.: Высшая школа, 1978.

26. ЗЗ.Интерфейсы систем обработки данных: Справочник/ A.A. Мячев, В.Н. Степанов, В.К. Щербо; Под ред. A.A. Мячева. М.: Радио и связь, 1989.34.0вчинников В.В., Рыбкин И.И. Техническая база интерфейсов локальных вычислительных сетей. М.: Радио и связь, 1989.

27. Дженнингс Ф. Практическая передача данных: Модемы, сети и протоколы: Пер. с англ. -М.: Мир, 1989.

28. Зб.Блэк Ю. Сети ЭВМ: Протоколы, стандарты, интерфейсы: Пер. с англ-М.: Мир, 1990.37Лернега B.C., Василенко В.А., Бондарев В.Н. Расчёт и проектирование технических средств обмена и передачи информации. М.: Высшая школа, 1990.

29. Фролов A.B., Фролов Г.В. Локальные сети персональных компьютеров. М.: ДИАЛОГ - МИФИ, 1993.

30. Лапшинский A.B. Локальные сети персональных компьютеров: В 2-х ч. -М.: МИФИ, 1994.

31. Нанс Б. Компьютерные сети: Пер. с англ. М.: БИНОМ, 1996.

32. Spurgeon Ch. Ethernet Configuration Guidelines. Peer-to-Peer

33. Communications, Inc., 1996.

34. Gigabit Ethernet. Gigabit Ethernet Alliance, 2000.

35. Новиков Ю.В., Калашников O.A., Гуляев С.Э. Разработка устройств сопряжения для персональных компьютеров типа IBM PC. Под общ. ред. Ю.В. Новикова. М.: ЭКОМ, 1997.

36. Гук М. Аппаратные средства IBM PC. Энциклопедия. СПб: Питер Ком, 1999.

37. PCI BIOS Specification. Revision 2.0. PCI Special Interest Grope, 1993.

38. PCI LOCAL BUS. Revision 2.2. PCI Special Interest Grope, 1999.

39. PCI Special Interest Grope (http://www.pcisig.com)