Параллельное программирование

Сетевые технологии параллельного программирования

Разбить на страницы
Показывать лекцию целиком

Концепция построения вычислительных комплексов на базе локальной вычислительной сети

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

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

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

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

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

Сетью ЭВМ называется комплекс территориально рассредоточенных ЭВМ и терминальных устройств, связанных каналами передачи данных.

Сейчас сложилась такая практика, что с сетями ЭВМ связывают более общее понятие — информационная система. Однако изначально целью создания сетей ЭВМ было:

  • Совместное использование суммарных вычислительных ресурсов. (Данная цель характерна на ранней стадии распространения сетей. Когда-то восторг вызывало то, что задача, введенная в Нью-Йорке, в действительности решалась в Париже — в соответствии с наличием вычислительных ресурсов.)
  • Обеспечение широкого диапазона решаемых задач, предъявляющих повышенные требования к производительности и объему памяти. (На возможность распараллеливания возлагались также надежды на этапе разработки первых сетей ЭВМ. Однако возврат к этой идее наблюдается сейчас: в распределенных вычислительных комплексах, используемых в системах управления, в том числе — бортовых, все настойчивее изыскиваются возможности применения сетевых технологий, весьма продвинутых в направлении стандартизованного оперативного обмена.)
  • Обеспечение высокой надежности систем обработки информации (за счет возможности перераспределения выделяемых ресурсов).
  • Совместное и взаимное информационное обслуживание, расширение сети пользователей ЭВМ, развитие качественно новых средств коммуникаций. (Обмен данными и совместное использование централизованных или распределенных банков данных.)
  • Социальный прогресс, обусловленный культурным, научным, деловым обменом, общедоступностью информации наряду с возможностями адресной передачи. (Качественно новый уровень достигнут в культурном обмене, в дистанционном обучении, в проведении научных конференций, в демонстрационном показе и рекламе, в деловых контактах, в оперативности передачи значительных объемов данных по Еmail электронной почте и т.д.)
    •

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

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

    Сказанное выше тем более важно сейчас, когда умы охватывает идея Grid -технологий — технологий предоставления сетью (включая Интернет) виртуальных ресурсов по запросам на решение сложных вычислительных задач.

    Сложность алгоритма и проблема распараллеливания

    Ранее уже использовалось понятие сложности. Рассмотрим его полнее.

    Пусть задан некоторый алгоритм A. Почти всегда существует параметр n, характеризующий объем его данных. Пусть функция T(n) — время выполнения A, а f — некоторая функция от n. Говорят, что алгоритм A имеет теоретическую (асимптотическую) сложность O(f(n)), если

    $$\frac{T(n)}{f(n)} \xrightarrow[n\rightarrow\infty]{}k$$,

    где k — действительное.

    Если алгоритм выполняется за фиксированное время, не зависящее от размера задачи, говорят, что его сложность равна O (1).

    Это определение обобщается в случае, если время выполнения существенно зависит от нескольких параметров. Например, алгоритм, определяющий, входит ли множество m элементов в множество n элементов, может иметь, в зависимости от используемых структур данных, сложность O (m n) или O (m+n).

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

  • максимальную сложность, определяемую значением Tmax(n) — время выполнения алгоритма, когда выбранный набор n данных порождает наиболее долгое время выполнения алгоритма;
  • среднюю сложность, определяемую значением Tср(n) — средним временем выполнения алгоритма, примененного к n произвольным данным.
    •

    Эти понятия без труда распространяются на измерение сложности в единицах объема памяти: можно говорить о средней и максимальной пространственной сложности.

    Самыми лучшими являются линейные алгоритмы, имеющие сложность порядка an=b. Они называются также алгоритмами порядка O(n) где n — размерность входных данных. Такие алгоритмы действительно существуют. Например, сложение двух чисел столбиком в случае, если одно из них состоит из n, а другое — из m цифр, требует не более max(n, m) сложений и не более max(n, m) запоминаний. Т.е. данный алгоритм имеет сложность порядка O(n+m). Разумеется, это выражение показывает только порядок величины — постоянные факторы в нем не учитываются.

    Обобщение линейности дает нам первый большой класс алгоритмов — полиномиальных.

    Полиномиальным (или алгоритмом полиномиальной временной сложности) называется алгоритм, у которого временная сложность есть O(p(n)), где p(n) — полином от n. Задачи, где для решения известен алгоритм, сложность которого составляет полином заданной, постоянной и не зависящей от размерности входной величины n степени, называют "хорошими" и относят их к классу P.

    Экспоненциальной по природе считается задача сложностью не менее порядка xn, где x — константа или полином от n. Например, это задачи, в которых возможное число ответов уже экспоненциально. В частности, к ним относятся задачи, где требуется построить все подмножества заданного множества или все поддеревья заданного графа. Экспоненциальные задачи относят к классу E.

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

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

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

    Для большей убедительности и сравнения полиномиальных и экспоненциальных алгоритмов приведем таблицу, где единица времени — 1 мкс, а сложность совпадает с необходимым количеством единиц времени для обработки набора n данных:

    Сложность и время выполнения
    СложностьРазмер задачи — n
    102030405060
    n0.00001 с 0.00002 с 0.00003 с 0.00004 с 0.00005 с 0.00006 с
    n $${}^2$$ 0.0001 с 0.0004 с 0.0009 с 0.0016 с 0.0025 с 0.0036 с
    n $${}^3$$ 0.001 с 0.008 с 0.027 с 0.064 с 0.125 с 0.216 с
    n50.1 с 3.2 с 24.3 с 1.7 мин 5.2 мин 13.0 мин
    2n0.01 с 1.0 с 17.9 мин 12.7 дней 35.7 лет 366 веков
    3n0.59 с 58 мин 6.5 лет 3855 веков 2x108 веков 1.3x1013 веков

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

    Уточним понятие сложности для итеративных и рекурсивных алгоритмов.

    Отнесем к итеративным алгоритмам и те, к которым сводятся рекурсивные алгоритмы (например, вычисление факториала n!). Тогда время их выполнения (в случае сходящегося процесса) зависит от главного условия повторения итерации, например, от требуемой точности. Если мы установим время или сложность одной итерации, то сможем умножением на число итераций установить максимальную или среднюю сложность. Число итераций устанавливается теоретически или экспериментально. Например, так можно сделать при расчете значений функций по их разложению в ряд.

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

    Для большинства конечно-разностных схем решения дифференциальных уравнений методом сеток можно считать, что сложность одной итерации составляет O(n2) или O(n x m), где n2 — количество узлов при равном разбиении по x и по y, а nx m — то же количество при различающемся разбиении по осям. Увеличение количества узлов, покрывающих ту же область, т.е. уменьшение hx и hy, увеличивает скорость сходимости - и, соответственно, уменьшает число итераций, но сложность каждой итерации растет квадратично. Значит, необходим компромисс, который достигается посредством изучения поведения процесса, как на теоретическом, так и на экспериментальном уровне, вплоть до автоматической коррекции шагов в процессе вычислений в зависимости от локального поведения аппроксимаций производных. Т.е. шаги становятся непостоянными во всей области.

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

    Имеется широко распространенное соглашение, по которому задача не считается "хорошо решаемой", пока для нее не получен полиномиальный алгоритм. Задача называется труднорешаемой, если для ее решения не существует полиномиального алгоритма.

    Эта градация относительна, ибо сложность определяется по наихудшему варианту. Хотя реализация метода "ветвей и границ" — труднорешаемая задача (при теоретической оценке по максимальной сложности), сейчас для многих задач известны такие алгоритмы, которые практически очень быстро находят решение именно методом ветвей и границ.

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

    Полиномиальные по сложности алгоритмы относят к классу P -сложных. Среди экспоненциальных выделяют алгоритмы, основанные на переборе, и их относят в класс NP -сложных. Т.е. формально возможно существование экспоненциальных алгоритмов, основанных не на переборе. Например, n!, растущий быстрее, чем 2n. К NP -сложным относятся, например, задачи линейного целочисленного программирования, составление расписания, поиск кратчайшего пути в лабиринте и т.д. Обратим внимание, что все это так называемые дискретные задачи — на основе "неделимых" объектов.

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

    Требования к средствам операционного взаимодействия в локальной вычислительной сети

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

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

  • Распределение данных ( Data Sharing ). Данные в сети хранятся на центральном РС и могут быть доступны для любого РС, подключенного к сети, поэтому не надо на каждом рабочем месте хранить одну и ту же информацию.
  • Распределение ресурсов ( Resource Sharing ). Периферийные устройства могут быть доступны для всех пользователей сети, например: принтер, факс-модем, сканер, диски, выход в глобальную сеть.
  • Распределение программ ( Software Sharing ). Все пользователи сети могут иметь доступ к программам, которые были один раз централизованно установлены.
  • Электронная почта ( Electronic Mail ). Все пользователи сети могут передавать и принимать сообщения.
  • Обеспечение широкого диапазона решаемых задач, предъявляющих повышенные требования к производительности и объему памяти.
    •

    Локальные сети имеют некоторые особенности.

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

    При построении сетей ЭВМ, в т.ч. локальных, говорят о их топологии.

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

    Звездообразная сеть IBM Token Ring, ARCnet)

    "Звезда" — принципиально централизованная топология (рис. 3.1), в которой всегда есть четко выделенный центральный абонент, осуществляющий все управление обменом в сети, и через который идет вся информация в сети. В этом есть свои плюсы и минусы. Любое жестко централизованное управление по своей сути бесконфликтно, но такая сеть не будет работать при любой неисправности центрального абонента. Поэтому центральный компьютер должен отличаться от остальных высокой надежностью, а, следовательно, и более высокой стоимостью. К тому же, выполнять другие задачи на центральном компьютере станет невозможно, так как он будет загружен работой с сетью. К недостаткам топологии относится также ограниченное число абонентов, которое обычно в локальных сетях не превышает 16 пользователей. Затруднительно соединение звезд между собой. К плюсам данной конфигурации можно отнести ее малую чувствительность к выходу из строя соединительного кабеля. Разрыв кабеля в любом месте всегда нарушает связь только с одним абонентом.

    (рис 3.1) Сеть типа "звезда"

    Кольцевая сеть FDDI, IBM Token Ring)

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

    (рис 3.2) "Кольцевая" сеть

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

    Шинная организация (Ethernet, ARCnet)

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

    (рис 3.3) Сеть с общей шиной

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

    Сравнение топологий сетей
    ПараметрыЗвездаКольцоШина
    1. ОтказоустойчивостьВыход из строя одного PC не влияет на работоспособность сети Выход из строя одного PC может вывести из строя всю сеть Выход из строя кабеля останавливает работу многих пользователей
    2. Количество абонентов16 1024 и выше 1024 и выше
    3. Изменение количества абонентовВозможно Требует остановки всей сети Легко изменяется
    4. Влияние на общую стоимость сетиДополнительные затраты на центральный компьютер Дополнительные затраты на адаптер, выполняющий функции диспетчера сети Дешевая среда передачи
    5. Возможность управления обменомЦентрализованное Централизованное и децентрализованное Децентрализованное
    6. ОсобенностиМощность всей сети зависит от сервера Количество пользователей не оказывает сильного влияния на производительность. Трудно локализовать проблемы Оптоволоконные кабели не применяются. При значительных объёмах трафика уменьшается пропускная способность. Трудно локализовать проблемы.
    7. Протяженность До нескольких десятков километров
    8. ПрименениеВ зависимости от предъявляемых требований

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

    Управление обменом в сети типа "шина"

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

    (рис 3.4) Сеть с общей шиной — логическая "звезда"

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

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

    Можно отметить ряд существующих методов обмена в сетях шинной архитектуры.

  • Простейший метод, используемый при выбранном коде обмена NRZ в сравнительно медленных сетях, — децентрализованный кодовый приоритетный арбитраж. Данный метод арбитража был предложен Институтом Проблем Управления (ИПУ) еще в начале 1970-х годов. Он характеризуется низкой скоростью передачи, но высокой надежностью. Все абоненты имеют собственные приоритеты, которые могут динамически изменяться в зависимости от важности информации. При малой интенсивности обмена все абоненты равноправны (вероятность столкновений очень мала). Величина времени доступа к сети здесь не может быть гарантирована, так как абоненты с высокими приоритетами могут надолго занять сеть, не позволяя начать передачу абонентам с низкими приоритетами.

  • Второй метод, используемый в шине, — децентрализованный временной приоритетный арбитраж или метод доступа (рис. 3.5). Этот метод управления обменом обеспечивает более высокую скорость обмена, чем предыдущий (поскольку здесь нет ограничения на длительность каждого бита). Практически реализовать его так же сложно, как и предыдущий (каждый абонент должен отсчитывать свой временной интервал). Недостаток метода состоит также в том, что в случае большой длины сети и большого количества абонентов задержки становятся очень большими. Пример: при длине сети 1км, задержке сигнала в кабеле 4 нс/м и количестве абонентов 256 двойное время прохождения сигнала в сети 2L/V ( L — полная длина сети, V — скорость распространения сигнала в используемом кабеле), или минимальная задержка составит 8 мкс. Следовательно, для абонента с сетевым адресом 255 задержка будет уже равна 255*8мкс=2040 мкс, т.е. около 2 мс, что уже довольно существенно. Для сравнения: если пакет имеет размер 1 Кбайт, то при скорости передачи 10 Мбит/с его длительность будет всего 0,8 мс. Данный метод не имеет жесткой привязки к коду передачи информации (в предыдущем методе можно было использовать NRZ). Код может быть практически любым, главное — выбрать его таким, чтобы можно было определять занятость сети.

    (рис 3.5) Обмен методом доступа

  • Третий метод, получивший довольно широкое распространение, можно считать развитием второго. Называется он CSMA/CD (Carrier-Sense Multiple Access/Collision Detection) или по-русски МДКН/ОК — метод доступа с контролем несущей и обнаружением коллизий (столкновений). Идея метода состоит в том, чтобы уравнять в правах всех абонентов в любой возможной ситуации, то есть добиться, чтобы не было больших и малых фиксированных приоритетов (как в случае второго метода). Для этого используются времена задержки, вычисляемые каждым абонентом по определенному алгоритму.

    К достоинствам метода CSMA/CD можно отнести полное равноправие всех абонентов, то есть ни один из них не может надолго захватить сеть. Метод достаточно надежен: ведь в течение всего времени передачи пакета идет контроль столкновений. К недостаткам метода относится то, что он не исключает повторения столкновений, а также плохо держит высокую нагрузку в сети. Обычно считается, что он хорош только до тех пор, пока нагрузка не превышает 30%, то есть только 30% времени сеть занята, а 70% времени — свободна. Для сети Ethernet в среднем считается предельно допустимым 50-100 абонентов, иначе возможны существенные нарушения обмена. Основной недостаток метода — негарантированное время доступа: нельзя сказать наверняка, через сколько времени пакет точно дойдет до приемника. В этом отношении он хуже, чем методы централизованного управления (методы опроса).

    •

    Локальная сеть Ethernet

    В настоящее время разными фирмами разработаны стандарты ЛВС, поддержанные аппаратно и программно. Наиболее распространенным стандартом, соответствующим требованиям режима вычислительного комплекса, является локальная сеть ETHERNET. (Спецификацию разработали компании Xerox Corporation, Digital Equipment Corporation (DEC), Intel Corporation.)

    На базе Ethernet разработан стандарт IEEE 802.3. Сеть предполагает несколько конфигураций. Использует коаксиальный или оптоволоконный кабель.

    Применяется топология "шина", т.е.:

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

    Для организации взаимодействия станций в сети используется метод Множественного Доступа с Контролем Несущей и Обнаружением Столкновений (МДКН/ОС) — Carrier Sense Multiple Access / Collision Detection (CSMA/CD).

    Контроль Несущей: во время работы станция постоянно проверяет среду передачи. Передающая среда может быть

  • свободна, т.е. ни одна другая станция не передает данные;
  • занята, т.е. идет передача данных другой станцией.
    •

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

    Обнаружение Столкновений (Коллизий): станция, обнаружившая коллизию, выдает другим станциям специальный сигнал, по которому переданная информация считается недостоверной. После этого каждая станция делает повторную попытку передачи через специально найденное ею случайное время. Разное для всех станций случайное смещение времени повторной передачи служит высокой вероятности избежания коллизии. (Оригинальный способ избежать централизованного управления!) Если за 16 попыток станция не смогла передать пакет, считается, что среда неисправна. В локальную сеть всегда входит несколько абонентов, и каждый из них в любой момент времени может обратиться к сети. Поэтому требуется управление обменом с целью упорядочения использования сети различными абонентами, предотвращение или разрешение конфликтов между ними. В противном случае возможно искажение передаваемой информации. Для управления обменом (или управлением доступом к сети, или арбитража сети) используются различные методы, особенности которых определяются выбранной топологией сети.

    Организация параллельного решения задачи в локальной сети

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

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

    По рис. 1.12 из курса "Архитектура параллельных вычислительных систем" мы можем полностью представить различные планы параллельного решения рассмотренной задачи.

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

    Другая стратегия распределения узлов между процессорами может быть основана на делении области задания функции между процессорами. Т.е. вся область D на рис. 1.12 из курса "Архитектура параллельных вычислительных систем" может быть разделена поровну между процессорами ВС или станциями сети.

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

    Равноправие процессоров (симметричность) делают целесообразным использование шинной архитектуры ЛВС. (Отметим, что на ранней стадии построения вычислительных комплексов применялась именно шинная архитектура, как наиболее простая и естественная. То же можно отметить и относительно многих современных и перспективных мультимикропроцессорных систем.) Распространенным стандартом такой архитектуры, обусловившим разработку широкой номенклатуры аппаратных средств, является сеть ETHERNET. Параллельный вычислительный процесс должен воспроизводить технологию SPMD, основанную на применении способа распараллеливания по информации.

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

  • Исследуется задача и выделяется основной массив данных (одномерный или многомерный), обработку которого целесообразно распределить между станциями ЛВС, — опорный массив.
  • Формируется план распределения элементов опорного массива для обработки станциями сети. Разнообразие таких планов порождает и разнообразие возможных способов переадресации. Например, весь опорный массив может быть поровну (со следующими подряд элементами) поделен между станциями. Такой способ может применяться в случае, если длина массива не изменяется динамически. Более универсален способ распределения элементов опорного массива, когда после "расчета по n " каждый из них оказывается закрепленным за станцией с тем же номером. Это в точности соответствует технологии SPMD и поддержано системой команд. Такое распределение допускает динамическое изменение длин массивов (поддерживает динамический тип данных), что крайне важно при обработке баз знаний.
  • Составляется единственная для всех станций (предполагается их программная совместимость), универсальная программа циклической обработки элементов опорного массива, закрепленных за одной станцией. Программа должна содержать критический интервал обмена данными между станциями в необходимых (по алгоритму) направлениях. При этом запрос с последующим ожиданием данных (принцип редукционных вычислительных систем) должен отсутствовать, данные должны только отправляться. Это значит, что программы должны "уметь" ждать необходимые для себя данные. Поэтому становится целесообразным воспроизведение принципа data flow с помощью "почтовых ящиков".
  • Составляется программа ввода, визуализации и управления вычислительным процессом для станции (персонального компьютера), который назначается мониторным.
  • Задача решается в диалоговом режиме. Дело в том, что при большом времени собственно решения вмешательство пользователя (оператора) может быть не только неизбежным, но и желательным. Например, нахождение всех экстремумов функции можно автоматизировать следующим образом: разделить область задания функции между компьютерами и поручить им полностью исследовать свои подобласти; затем заставить их совместно исследовать полученные результаты и выделить глобальные экстремумы и др. Вторая задача может оказаться существенно сложнее. В то же время оператором она может быть решена значительно проще при достаточной визуализации. Принятое им решение может быть немедленно использовано при последующем автоматическом решении этой или другой задачи.
    •

    Рассмотрим конкретный возможный план решения рассмотренной выше задачи методом "сеток". Для простоты положим число используемых процессоров равным 2. В основу плана положим способ разделения области D между процессорами поровну. Зафиксируем hx = hy = h, определив тем самым количество узлов сетки в каждой строке и в каждом столбце. На рисунке 3.6 отражены выбранные количества узлов в строках и столбцах. Первая и последняя строка, как и первый и последний столбец, соответствуют узлам, в которых заданы граничные значения функции-решения.

    (рис 3.6) Распределение данных между двумя процессорами для решения задачи методом "сеток"

    Область D1, обрабатываемая процессором 1, определяется границами индекса i и координаты x:$$\begin{align*} 0 \le i \le \left [\frac{n}{2}\right] \\ 0 \le x \le \left [\frac{n}{2}\right]\cdot h \end{align*}$$

    Область D2, обрабатываемая процессором 2, определяется границами индекса i и координаты x:$$\begin{align*} \left [\frac{n}{2}\right] + 1 \le i \le - 1 \\ \left (\left [\frac{n}{2}\right] + 1\right)\cdot h \le x \le (n - 1)h = A \end{align*}$$

    По второй координате 0 <= y <=t (m - 1)h = B.

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

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

    В соответствии с граничными условиями

    fi0 = f1(ih,0) i = 0, ..., n - 1,

    fi,m-1 = f2(ih,(m-1)h=B) i = 0, ..., n - 1,

    f0j = f3(0,jh) j = 0, ..., m - 1,

    fn-1,j = f4((n-1)h=A,j) j = 0, ..., m - 1.

    Нулевое приближение значений fij может быть рассчитано по формулам интерполяции с усреднением:$$\begin{align*} f_{ij} = \frac{1}{2} \left[ \left( \frac {f_{n-1,j}-f_{0,j}}{n-1}\cdot i+f_{0,j}\right)+\left( \frac {f_{i,m-1}-f_{i,0}}{m-1}\cdot j+f_{i,0}\right)\right] \end{align*}$$

    для всех 0 < i < A, 0 < j < B.

    Итерационная формула имеет общий вид fij = F(fi-1,j, fi+1,j, fi,j-1, fi,j+1).

    Страницы:

    Концепция построения вычислительных комплексов на базе локальной вычислительной сети

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

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

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

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

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

    Сетью ЭВМ называется комплекс территориально рассредоточенных ЭВМ и терминальных устройств, связанных каналами передачи данных.

    Сейчас сложилась такая практика, что с сетями ЭВМ связывают более общее понятие — информационная система. Однако изначально целью создания сетей ЭВМ было:

  • Совместное использование суммарных вычислительных ресурсов. (Данная цель характерна на ранней стадии распространения сетей. Когда-то восторг вызывало то, что задача, введенная в Нью-Йорке, в действительности решалась в Париже — в соответствии с наличием вычислительных ресурсов.)
  • Обеспечение широкого диапазона решаемых задач, предъявляющих повышенные требования к производительности и объему памяти. (На возможность распараллеливания возлагались также надежды на этапе разработки первых сетей ЭВМ. Однако возврат к этой идее наблюдается сейчас: в распределенных вычислительных комплексах, используемых в системах управления, в том числе — бортовых, все настойчивее изыскиваются возможности применения сетевых технологий, весьма продвинутых в направлении стандартизованного оперативного обмена.)
  • Обеспечение высокой надежности систем обработки информации (за счет возможности перераспределения выделяемых ресурсов).
  • Совместное и взаимное информационное обслуживание, расширение сети пользователей ЭВМ, развитие качественно новых средств коммуникаций. (Обмен данными и совместное использование централизованных или распределенных банков данных.)
  • Социальный прогресс, обусловленный культурным, научным, деловым обменом, общедоступностью информации наряду с возможностями адресной передачи. (Качественно новый уровень достигнут в культурном обмене, в дистанционном обучении, в проведении научных конференций, в демонстрационном показе и рекламе, в деловых контактах, в оперативности передачи значительных объемов данных по Еmail электронной почте и т.д.)
    •

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

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

    Сказанное выше тем более важно сейчас, когда умы охватывает идея Grid -технологий — технологий предоставления сетью (включая Интернет) виртуальных ресурсов по запросам на решение сложных вычислительных задач.

    Сложность алгоритма и проблема распараллеливания

    Ранее уже использовалось понятие сложности. Рассмотрим его полнее.

    Пусть задан некоторый алгоритм A. Почти всегда существует параметр n, характеризующий объем его данных. Пусть функция T(n) — время выполнения A, а f — некоторая функция от n. Говорят, что алгоритм A имеет теоретическую (асимптотическую) сложность O(f(n)), если

    $$\frac{T(n)}{f(n)} \xrightarrow[n\rightarrow\infty]{}k$$,

    где k — действительное.

    Если алгоритм выполняется за фиксированное время, не зависящее от размера задачи, говорят, что его сложность равна O (1).

    Это определение обобщается в случае, если время выполнения существенно зависит от нескольких параметров. Например, алгоритм, определяющий, входит ли множество m элементов в множество n элементов, может иметь, в зависимости от используемых структур данных, сложность O (m n) или O (m+n).

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

  • максимальную сложность, определяемую значением Tmax(n) — время выполнения алгоритма, когда выбранный набор n данных порождает наиболее долгое время выполнения алгоритма;
  • среднюю сложность, определяемую значением Tср(n) — средним временем выполнения алгоритма, примененного к n произвольным данным.
    •

    Эти понятия без труда распространяются на измерение сложности в единицах объема памяти: можно говорить о средней и максимальной пространственной сложности.

    Самыми лучшими являются линейные алгоритмы, имеющие сложность порядка an=b. Они называются также алгоритмами порядка O(n) где n — размерность входных данных. Такие алгоритмы действительно существуют. Например, сложение двух чисел столбиком в случае, если одно из них состоит из n, а другое — из m цифр, требует не более max(n, m) сложений и не более max(n, m) запоминаний. Т.е. данный алгоритм имеет сложность порядка O(n+m). Разумеется, это выражение показывает только порядок величины — постоянные факторы в нем не учитываются.

    Обобщение линейности дает нам первый большой класс алгоритмов — полиномиальных.

    Полиномиальным (или алгоритмом полиномиальной временной сложности) называется алгоритм, у которого временная сложность есть O(p(n)), где p(n) — полином от n. Задачи, где для решения известен алгоритм, сложность которого составляет полином заданной, постоянной и не зависящей от размерности входной величины n степени, называют "хорошими" и относят их к классу P.

    Экспоненциальной по природе считается задача сложностью не менее порядка xn, где x — константа или полином от n. Например, это задачи, в которых возможное число ответов уже экспоненциально. В частности, к ним относятся задачи, где требуется построить все подмножества заданного множества или все поддеревья заданного графа. Экспоненциальные задачи относят к классу E.

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

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

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

    Для большей убедительности и сравнения полиномиальных и экспоненциальных алгоритмов приведем таблицу, где единица времени — 1 мкс, а сложность совпадает с необходимым количеством единиц времени для обработки набора n данных:

    Сложность и время выполнения
    СложностьРазмер задачи — n
    102030405060
    n0.00001 с 0.00002 с 0.00003 с 0.00004 с 0.00005 с 0.00006 с
    n $${}^2$$ 0.0001 с 0.0004 с 0.0009 с 0.0016 с 0.0025 с 0.0036 с
    n $${}^3$$ 0.001 с 0.008 с 0.027 с 0.064 с 0.125 с 0.216 с
    n50.1 с 3.2 с 24.3 с 1.7 мин 5.2 мин 13.0 мин
    2n0.01 с 1.0 с 17.9 мин 12.7 дней 35.7 лет 366 веков
    3n0.59 с 58 мин 6.5 лет 3855 веков 2x108 веков 1.3x1013 веков

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

    Уточним понятие сложности для итеративных и рекурсивных алгоритмов.

    Отнесем к итеративным алгоритмам и те, к которым сводятся рекурсивные алгоритмы (например, вычисление факториала n!). Тогда время их выполнения (в случае сходящегося процесса) зависит от главного условия повторения итерации, например, от требуемой точности. Если мы установим время или сложность одной итерации, то сможем умножением на число итераций установить максимальную или среднюю сложность. Число итераций устанавливается теоретически или экспериментально. Например, так можно сделать при расчете значений функций по их разложению в ряд.

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

    Для большинства конечно-разностных схем решения дифференциальных уравнений методом сеток можно считать, что сложность одной итерации составляет O(n2) или O(n x m), где n2 — количество узлов при равном разбиении по x и по y, а nx m — то же количество при различающемся разбиении по осям. Увеличение количества узлов, покрывающих ту же область, т.е. уменьшение hx и hy, увеличивает скорость сходимости - и, соответственно, уменьшает число итераций, но сложность каждой итерации растет квадратично. Значит, необходим компромисс, который достигается посредством изучения поведения процесса, как на теоретическом, так и на экспериментальном уровне, вплоть до автоматической коррекции шагов в процессе вычислений в зависимости от локального поведения аппроксимаций производных. Т.е. шаги становятся непостоянными во всей области.

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

    Имеется широко распространенное соглашение, по которому задача не считается "хорошо решаемой", пока для нее не получен полиномиальный алгоритм. Задача называется труднорешаемой, если для ее решения не существует полиномиального алгоритма.

    Эта градация относительна, ибо сложность определяется по наихудшему варианту. Хотя реализация метода "ветвей и границ" — труднорешаемая задача (при теоретической оценке по максимальной сложности), сейчас для многих задач известны такие алгоритмы, которые практически очень быстро находят решение именно методом ветвей и границ.

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

    Полиномиальные по сложности алгоритмы относят к классу P -сложных. Среди экспоненциальных выделяют алгоритмы, основанные на переборе, и их относят в класс NP -сложных. Т.е. формально возможно существование экспоненциальных алгоритмов, основанных не на переборе. Например, n!, растущий быстрее, чем 2n. К NP -сложным относятся, например, задачи линейного целочисленного программирования, составление расписания, поиск кратчайшего пути в лабиринте и т.д. Обратим внимание, что все это так называемые дискретные задачи — на основе "неделимых" объектов.

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

    Требования к средствам операционного взаимодействия в локальной вычислительной сети

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

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

  • Распределение данных ( Data Sharing ). Данные в сети хранятся на центральном РС и могут быть доступны для любого РС, подключенного к сети, поэтому не надо на каждом рабочем месте хранить одну и ту же информацию.
  • Распределение ресурсов ( Resource Sharing ). Периферийные устройства могут быть доступны для всех пользователей сети, например: принтер, факс-модем, сканер, диски, выход в глобальную сеть.
  • Распределение программ ( Software Sharing ). Все пользователи сети могут иметь доступ к программам, которые были один раз централизованно установлены.
  • Электронная почта ( Electronic Mail ). Все пользователи сети могут передавать и принимать сообщения.
  • Обеспечение широкого диапазона решаемых задач, предъявляющих повышенные требования к производительности и объему памяти.
    •

    Локальные сети имеют некоторые особенности.

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

    При построении сетей ЭВМ, в т.ч. локальных, говорят о их топологии.

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

    Звездообразная сеть IBM Token Ring, ARCnet)

    "Звезда" — принципиально централизованная топология (рис. 3.1), в которой всегда есть четко выделенный центральный абонент, осуществляющий все управление обменом в сети, и через который идет вся информация в сети. В этом есть свои плюсы и минусы. Любое жестко централизованное управление по своей сути бесконфликтно, но такая сеть не будет работать при любой неисправности центрального абонента. Поэтому центральный компьютер должен отличаться от остальных высокой надежностью, а, следовательно, и более высокой стоимостью. К тому же, выполнять другие задачи на центральном компьютере станет невозможно, так как он будет загружен работой с сетью. К недостаткам топологии относится также ограниченное число абонентов, которое обычно в локальных сетях не превышает 16 пользователей. Затруднительно соединение звезд между собой. К плюсам данной конфигурации можно отнести ее малую чувствительность к выходу из строя соединительного кабеля. Разрыв кабеля в любом месте всегда нарушает связь только с одним абонентом.

    (рис 3.1) Сеть типа "звезда"

    Кольцевая сеть FDDI, IBM Token Ring)

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

    (рис 3.2) "Кольцевая" сеть

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

    Шинная организация (Ethernet, ARCnet)

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

    (рис 3.3) Сеть с общей шиной

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

    Сравнение топологий сетей
    ПараметрыЗвездаКольцоШина
    1. ОтказоустойчивостьВыход из строя одного PC не влияет на работоспособность сети Выход из строя одного PC может вывести из строя всю сеть Выход из строя кабеля останавливает работу многих пользователей
    2. Количество абонентов16 1024 и выше 1024 и выше
    3. Изменение количества абонентовВозможно Требует остановки всей сети Легко изменяется
    4. Влияние на общую стоимость сетиДополнительные затраты на центральный компьютер Дополнительные затраты на адаптер, выполняющий функции диспетчера сети Дешевая среда передачи
    5. Возможность управления обменомЦентрализованное Централизованное и децентрализованное Децентрализованное
    6. ОсобенностиМощность всей сети зависит от сервера Количество пользователей не оказывает сильного влияния на производительность. Трудно локализовать проблемы Оптоволоконные кабели не применяются. При значительных объёмах трафика уменьшается пропускная способность. Трудно локализовать проблемы.
    7. Протяженность До нескольких десятков километров
    8. ПрименениеВ зависимости от предъявляемых требований

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

    Управление обменом в сети типа "шина"

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

    (рис 3.4) Сеть с общей шиной — логическая "звезда"

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

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

    Можно отметить ряд существующих методов обмена в сетях шинной архитектуры.

  • Простейший метод, используемый при выбранном коде обмена NRZ в сравнительно медленных сетях, — децентрализованный кодовый приоритетный арбитраж. Данный метод арбитража был предложен Институтом Проблем Управления (ИПУ) еще в начале 1970-х годов. Он характеризуется низкой скоростью передачи, но высокой надежностью. Все абоненты имеют собственные приоритеты, которые могут динамически изменяться в зависимости от важности информации. При малой интенсивности обмена все абоненты равноправны (вероятность столкновений очень мала). Величина времени доступа к сети здесь не может быть гарантирована, так как абоненты с высокими приоритетами могут надолго занять сеть, не позволяя начать передачу абонентам с низкими приоритетами.

  • Второй метод, используемый в шине, — децентрализованный временной приоритетный арбитраж или метод доступа (рис. 3.5). Этот метод управления обменом обеспечивает более высокую скорость обмена, чем предыдущий (поскольку здесь нет ограничения на длительность каждого бита). Практически реализовать его так же сложно, как и предыдущий (каждый абонент должен отсчитывать свой временной интервал). Недостаток метода состоит также в том, что в случае большой длины сети и большого количества абонентов задержки становятся очень большими. Пример: при длине сети 1км, задержке сигнала в кабеле 4 нс/м и количестве абонентов 256 двойное время прохождения сигнала в сети 2L/V ( L — полная длина сети, V — скорость распространения сигнала в используемом кабеле), или минимальная задержка составит 8 мкс. Следовательно, для абонента с сетевым адресом 255 задержка будет уже равна 255*8мкс=2040 мкс, т.е. около 2 мс, что уже довольно существенно. Для сравнения: если пакет имеет размер 1 Кбайт, то при скорости передачи 10 Мбит/с его длительность будет всего 0,8 мс. Данный метод не имеет жесткой привязки к коду передачи информации (в предыдущем методе можно было использовать NRZ). Код может быть практически любым, главное — выбрать его таким, чтобы можно было определять занятость сети.

    (рис 3.5) Обмен методом доступа

  • Третий метод, получивший довольно широкое распространение, можно считать развитием второго. Называется он CSMA/CD (Carrier-Sense Multiple Access/Collision Detection) или по-русски МДКН/ОК — метод доступа с контролем несущей и обнаружением коллизий (столкновений). Идея метода состоит в том, чтобы уравнять в правах всех абонентов в любой возможной ситуации, то есть добиться, чтобы не было больших и малых фиксированных приоритетов (как в случае второго метода). Для этого используются времена задержки, вычисляемые каждым абонентом по определенному алгоритму.

    К достоинствам метода CSMA/CD можно отнести полное равноправие всех абонентов, то есть ни один из них не может надолго захватить сеть. Метод достаточно надежен: ведь в течение всего времени передачи пакета идет контроль столкновений. К недостаткам метода относится то, что он не исключает повторения столкновений, а также плохо держит высокую нагрузку в сети. Обычно считается, что он хорош только до тех пор, пока нагрузка не превышает 30%, то есть только 30% времени сеть занята, а 70% времени — свободна. Для сети Ethernet в среднем считается предельно допустимым 50-100 абонентов, иначе возможны существенные нарушения обмена. Основной недостаток метода — негарантированное время доступа: нельзя сказать наверняка, через сколько времени пакет точно дойдет до приемника. В этом отношении он хуже, чем методы централизованного управления (методы опроса).

    •

    Локальная сеть Ethernet

    В настоящее время разными фирмами разработаны стандарты ЛВС, поддержанные аппаратно и программно. Наиболее распространенным стандартом, соответствующим требованиям режима вычислительного комплекса, является локальная сеть ETHERNET. (Спецификацию разработали компании Xerox Corporation, Digital Equipment Corporation (DEC), Intel Corporation.)

    На базе Ethernet разработан стандарт IEEE 802.3. Сеть предполагает несколько конфигураций. Использует коаксиальный или оптоволоконный кабель.

    Применяется топология "шина", т.е.:

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

    Для организации взаимодействия станций в сети используется метод Множественного Доступа с Контролем Несущей и Обнаружением Столкновений (МДКН/ОС) — Carrier Sense Multiple Access / Collision Detection (CSMA/CD).

    Контроль Несущей: во время работы станция постоянно проверяет среду передачи. Передающая среда может быть

  • свободна, т.е. ни одна другая станция не передает данные;
  • занята, т.е. идет передача данных другой станцией.
    •

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

    Обнаружение Столкновений (Коллизий): станция, обнаружившая коллизию, выдает другим станциям специальный сигнал, по которому переданная информация считается недостоверной. После этого каждая станция делает повторную попытку передачи через специально найденное ею случайное время. Разное для всех станций случайное смещение времени повторной передачи служит высокой вероятности избежания коллизии. (Оригинальный способ избежать централизованного управления!) Если за 16 попыток станция не смогла передать пакет, считается, что среда неисправна. В локальную сеть всегда входит несколько абонентов, и каждый из них в любой момент времени может обратиться к сети. Поэтому требуется управление обменом с целью упорядочения использования сети различными абонентами, предотвращение или разрешение конфликтов между ними. В противном случае возможно искажение передаваемой информации. Для управления обменом (или управлением доступом к сети, или арбитража сети) используются различные методы, особенности которых определяются выбранной топологией сети.

    Организация параллельного решения задачи в локальной сети

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

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

    По рис. 1.12 из курса "Архитектура параллельных вычислительных систем" мы можем полностью представить различные планы параллельного решения рассмотренной задачи.

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

    Другая стратегия распределения узлов между процессорами может быть основана на делении области задания функции между процессорами. Т.е. вся область D на рис. 1.12 из курса "Архитектура параллельных вычислительных систем" может быть разделена поровну между процессорами ВС или станциями сети.

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

    Равноправие процессоров (симметричность) делают целесообразным использование шинной архитектуры ЛВС. (Отметим, что на ранней стадии построения вычислительных комплексов применялась именно шинная архитектура, как наиболее простая и естественная. То же можно отметить и относительно многих современных и перспективных мультимикропроцессорных систем.) Распространенным стандартом такой архитектуры, обусловившим разработку широкой номенклатуры аппаратных средств, является сеть ETHERNET. Параллельный вычислительный процесс должен воспроизводить технологию SPMD, основанную на применении способа распараллеливания по информации.

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

  • Исследуется задача и выделяется основной массив данных (одномерный или многомерный), обработку которого целесообразно распределить между станциями ЛВС, — опорный массив.
  • Формируется план распределения элементов опорного массива для обработки станциями сети. Разнообразие таких планов порождает и разнообразие возможных способов переадресации. Например, весь опорный массив может быть поровну (со следующими подряд элементами) поделен между станциями. Такой способ может применяться в случае, если длина массива не изменяется динамически. Более универсален способ распределения элементов опорного массива, когда после "расчета по n " каждый из них оказывается закрепленным за станцией с тем же номером. Это в точности соответствует технологии SPMD и поддержано системой команд. Такое распределение допускает динамическое изменение длин массивов (поддерживает динамический тип данных), что крайне важно при обработке баз знаний.
  • Составляется единственная для всех станций (предполагается их программная совместимость), универсальная программа циклической обработки элементов опорного массива, закрепленных за одной станцией. Программа должна содержать критический интервал обмена данными между станциями в необходимых (по алгоритму) направлениях. При этом запрос с последующим ожиданием данных (принцип редукционных вычислительных систем) должен отсутствовать, данные должны только отправляться. Это значит, что программы должны "уметь" ждать необходимые для себя данные. Поэтому становится целесообразным воспроизведение принципа data flow с помощью "почтовых ящиков".
  • Составляется программа ввода, визуализации и управления вычислительным процессом для станции (персонального компьютера), который назначается мониторным.
  • Задача решается в диалоговом режиме. Дело в том, что при большом времени собственно решения вмешательство пользователя (оператора) может быть не только неизбежным, но и желательным. Например, нахождение всех экстремумов функции можно автоматизировать следующим образом: разделить область задания функции между компьютерами и поручить им полностью исследовать свои подобласти; затем заставить их совместно исследовать полученные результаты и выделить глобальные экстремумы и др. Вторая задача может оказаться существенно сложнее. В то же время оператором она может быть решена значительно проще при достаточной визуализации. Принятое им решение может быть немедленно использовано при последующем автоматическом решении этой или другой задачи.
    •

    Рассмотрим конкретный возможный план решения рассмотренной выше задачи методом "сеток". Для простоты положим число используемых процессоров равным 2. В основу плана положим способ разделения области D между процессорами поровну. Зафиксируем hx = hy = h, определив тем самым количество узлов сетки в каждой строке и в каждом столбце. На рисунке 3.6 отражены выбранные количества узлов в строках и столбцах. Первая и последняя строка, как и первый и последний столбец, соответствуют узлам, в которых заданы граничные значения функции-решения.

    (рис 3.6) Распределение данных между двумя процессорами для решения задачи методом "сеток"

    Область D1, обрабатываемая процессором 1, определяется границами индекса i и координаты x:$$\begin{align*} 0 \le i \le \left [\frac{n}{2}\right] \\ 0 \le x \le \left [\frac{n}{2}\right]\cdot h \end{align*}$$

    Область D2, обрабатываемая процессором 2, определяется границами индекса i и координаты x:$$\begin{align*} \left [\frac{n}{2}\right] + 1 \le i \le - 1 \\ \left (\left [\frac{n}{2}\right] + 1\right)\cdot h \le x \le (n - 1)h = A \end{align*}$$

    По второй координате 0 <= y <=t (m - 1)h = B.

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

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

    В соответствии с граничными условиями

    fi0 = f1(ih,0) i = 0, ..., n - 1,

    fi,m-1 = f2(ih,(m-1)h=B) i = 0, ..., n - 1,

    f0j = f3(0,jh) j = 0, ..., m - 1,

    fn-1,j = f4((n-1)h=A,j) j = 0, ..., m - 1.

    Нулевое приближение значений fij может быть рассчитано по формулам интерполяции с усреднением:$$\begin{align*} f_{ij} = \frac{1}{2} \left[ \left( \frac {f_{n-1,j}-f_{0,j}}{n-1}\cdot i+f_{0,j}\right)+\left( \frac {f_{i,m-1}-f_{i,0}}{m-1}\cdot j+f_{i,0}\right)\right] \end{align*}$$

    для всех 0 < i < A, 0 < j < B.

    Итерационная формула имеет общий вид fij = F(fi-1,j, fi+1,j, fi,j-1, fi,j+1).

    Предыдущее занятие Следующее занятие
    Вернуться к учебному плану
    ^