Лекция 16.
Алгоритмларнинг коммуникацион мураккаблигини баҳолаш
Оценка коммуникационной трудоемкости алгоритмов
- Маълумотлар узатиш механизмларининг умумий характеристикаси
- Маршрутизация алгоритмлари
- Маълумотлар узатишнинг методлари
- Маълумотлар узатиш асосий операцияларининг мураккаблигини таҳлил қилиш
- Коммуникацион муҳитнинг топологияларини мантиқий тасаввур этиш методлари
- Кластер тизимлар учун маълумотлар узатиш операцияларининг мураккаблигини баҳолаш
Мазмуни
Кириш
- Мазкур бўлим параллел алгоритмлар бажарилганда юзага келадиган ахборот оқимларини таҳлил қилиш масалаларига бағишланган :
- Маълумотлар узатиш механизмларининг умумий тавсифи берилган,
- Ахборот алмашинуви асосий муракаблиги таҳлили келтирилган
- МВС структурасининг мантиқий тасаввур этиш методлари келтирилгани
Затраты на организацию взаимодействия при помощи передачи сообщений существенным образом влияют на эффективность параллельных вычислений
- Маршрутлаш алгоритмлари маълумотлар узатишнинг процессордан-манбагача бўлган йўлини белгилаб беради определяют путь передачи данных от процессора-источника сообщения до процессора, к которому сообщение должно быть доставлено:
- Оптимал бўлган йўлларни яъни энг қисқа йўлни ҳар доим аниқлайди ва нооптимал маршрутлаш алгоритмларни , определяющие всегда наикратчайшие пути передачи данных, и неоптимальные алгоритмы маршрутизации,
- Маршрутлаш танлашнинг детерминирланган ва адаптив методларини танлаш
выбора маршрутов (адаптивные алгоритмы определяют пути передачи данных в зависимости от существующей загрузки коммуникационных каналов).
Маълумотлар узатиш механизмларининг умумий характеристкаси Общая характеристика механизмов передачи данных…
Маршрутлаш алгоритмлари:
- маршрутлашнинг координаталар бўйича методи (dimension-ordered routing) – бу маршрутлашнинг энг кенг тарқалган оптимал методи ҳисобланади:
Маълумотларни узатиш йўлларини излаш ҳар бир тармоқ коммуникация топологияси ўлчами учун навбатма-навбат амалга оширилади Поиск путей передачи данных осуществляется поочередно для каждой размерности топологии сети коммуникации,
- Икки ўлчамли решетка учун : Маълумотларни узатиш аввал битта йўналиш бўйича , сўнгра эса маълумотлар бошқа йўналиш бўйича узатилади Для двумерной решетки: передача данных сначала выполняется по одному направлению, а затем данные передаются вдоль другого направления (алгоритм XY-маршрутизации),
- Гиперкуб учун :, процессорларнинг номерларидаги биринчи битли позиция билан аниқланадиган маълумотларни процессорга циклик узатишда, унда шу вақтда ахборот жойлашган бўлади ва шу номерга ахборот узатилиши керак бўлади.
- Для гиперкуба: циклическая передача данных процессору, определяемому первой различающейся битовой позицией в номерах процессоров, на котором сообщение располагается в данный момент времени и на который сообщение должно быть передано.
Маълумотлар узатиш механизмларининг умумий характеристикаси …
- Маълумотларни узатиш методлари …
Маълумотларни процессорлар ўртасида узатиш вақти параллел алгоритмни бажариш узунлигини коммуникацион ташкил этувчисини (communication latency) белгилайди. Время передачи данных между процессорами определяет коммуникационную составляющую (communication latency) длительности выполнения параллельного алгоритма.
Маълумотларни узатиш вақтини баҳолашда ишлатиладиган асосий параметрлар тўплами ўз ичига қуйидагиларни олади : Основной набор параметров, используемый при оценке времени передачи данных, включает:
- Бошланғич тайёргарлик вақти (tн) тармоқда ахборотни узатиш, маршрутни излаш ва ҳок.га кетадиган тайёргарлик вақт узунлигини белгилайди, время начальной подготовки (tн) характеризует длительность подготовки сообщения для передачи, поиска маршрута в сети и т.п.,
- Хизмат маълумотларини узатиш вақти (tс) иккита қўшни процессорлар (яъни ўрталарида маълумотларни узатиш учун физик канал мавжуд бўлган процессорлар учун), зизмат маълумотларига хабарнинг сарлавҳаси,хатоларни аниқлаш блоки ва бошқ. время передачи служебных данных (tс) между двумя соседними процессорами (т.е. для процессоров, между которыми имеется физический канал передачи данных); к служебным данным может относиться заголовок сообщения, блок данных для обнаружения ошибок передачи и т.п.,
- время передачи одного слова данных по одному каналу передачи данных (tк); длительность подобной передачи определяется полосой пропускания коммуникационных каналов в сети.
Маълумотлар узатиш механизмларининг умумий характеристикаси …
- Маълумотларни узатиш методлари …
Хабарларни узатиш методи (ХУМ) маълумотларни бўлакланмайдиган (атомар) ахборот бўлаклари (store-and-forward routing or SFR) сифатида узатади : Метод передачи сообщений (МПС) осуществляет передачу данных как неделимых (атомарных) блоков информации (store-and-forward routing or SFR):
- процессор, узатиш учун ахборотга эга бўлиб узатиш учун маълумотларнинг барча ҳажмига эга, маълумотларни қайси процессорга юбориш кераклигини аниқлайди,ва маълумотларни жўнатиш операциясини ишга туширади.процессор содержащий сообщение для передачи, готовит весь объем данных для передачи, определяет процессор, которому следует направить данные, и запускает операцию пересылки данных,
- Процессор, унга юборилган хабарни биринчи навбатда тўлиқ барча маълумотларни қабул қилади ва шундан сўнг қабул қилинган хабарни маршрут бўйича узатишни амалга оширади.
- процессор, которому направлено сообщение, в первую очередь осуществляет прием полностью всех пересылаемых данных и только затем приступает к пересылке принятого сообщения далее по маршруту.
Маълумотлар узатиш механизмларининг умумий характеристкаси …
- Маълумотларни узатиш методлари …
Маълумотларни узатиш методлари (МУМ)жўнатилаётган хабардарни кичик ўлчамдаги ахборотлар блоки (cut-through routing or CTR) кўринишида узатишга асосланган:
Метод передачи пакетов (МПП) основан на представлении пересылаемых сообщений в виде блоков информации меньшего размера (cut-through routing or CTR):
- Қабул қилаётган процессор маълумотларни кейинги маршрут бўйича жўнатишни барча хабарларни қабул қилинишини тамом бўлишини кутмай, бевосита навбатдаги пакетни қабул қилгандан сўнг амалга ошириши мумкин, принимающий процессор может осуществлять пересылку данных по дальнейшему маршруту непосредственно сразу после приема очередного пакета, не дожидаясь завершения приема данных всего сообщения.
Маълумотлар узатиш механизмларининг умумий характеристкаси …
- Маълумотларни узатиш методлари …
l узунликдаги маршрут бўйича m байт ўлчамли маълумот ларни узатиш вақти tпд қуйидагилар билан белгиланади: :
Время пересылки данных tпд размером m байт по маршруту длиной l определяется :
- Хабарларни узатиш методи учун Для метода передачи сообщений::
етарли даражада узун бўлган хабарларда хизмат маълумотларини узатишга кетадиган вақтни ҳисобламаса ҳам бўлади при достаточно длинных сообщениях временем пересылки служебных данных можно пренебречь:
- Пакетларни узатиш методи учун Для метода передачи пакетов:
- Гиперку́б — обобщение куба на случай с произвольным числом измерений. Гиперкубом размерности Ν называется множество точек в Ν-мерном евклидовом пространстве .
Маълумотлар узатиш механизмларининг умумий характеристкаси …
- Хабарлар узатиш методи
- Пакетларни узатиш методи
- (хабар 2 та пакета бўлинади)
- Пакетларни узатиш методи (хабар 4 та пакета бўлинади)
- Маълумотларни узатиш методлари …
Маълумотлар узатиш механизмларининг умумий характеристикаси …
- Пакетларни узатиш методи (қўллашни баҳолаш)Метод передачи пакетов (оценка применимости):
- Маълумотларни жуда тез узатишга олиб келади приводит к более быстрой пересылке данных,
- Жўнатилаётган маълумотларни сақлаш учун хабарларни жўнатиш-қабул қилишни ташкил этишда хотирага бўлган эҳтиёжни камайтиради снижает потребность в памяти для хранения пересылаемых данных для организации приема-передачи сообщений,
- Узатиш учун бир вақтнинг ўзида турли коммуникацион каналлар ишлатилиши мумкин для передачи могут использоваться одновременно разные коммуникационные каналы,
- Тармоқнинг мураккаброқ аппаратли ва дастурий таъминотини ишлаб чиқишни талаб қилади требует разработки более сложного аппаратного и программного обеспечения сети,
- может увеличить накладные расходы (время подготовки и время передачи служебных данных),
- при передаче пакетов возможно возникновение конфликтных ситуаций (дедлоков).
Маълумотлар узатиш механизмларининг умумий характеристкаси
Do'stlaringiz bilan baham: |
