Паралелни алгоритми в компютърните клъстери

KONSTANTIN
PRESLAVSKY
UNIVERSITY
S H U M E N

Ш У М Е Н С К И У Н И В Е Р С И Т Е Т
“Е П И С К О П К О Н С Т А Н Т И Н П Р Е С Л А В С К И ”
КУРСОВА
РАБОТА
По
Паралелни Алгоритми
На
тема
“
Паралелни алгоритми в компютърните
клъстери
.Реализация на
OpenMosix
клъстер”
Изготвил
:
Преподавател
:
Мартин
Иванов Петров

доц.д­р В. Хасанов
Ф№
: 4
40
Специалност
: Системно администриране
Магистърска
програма
Задочно
обучение
Първи
курс
Шумен
2009
Този
учебен материал е публикуван от потребител в www.referati.org

Съдържание
1.Увод
. Предизвикателствата на паралелната информационна обработка.
2.Компютърни
клъстери.
3.История
и характеристики на
Mosix, Mosix2
и
OpenMosix
4.Реализация
на
OpenMosix
клъстер.
Този
учебен материал е публикуван от потребител в www.referati.org

Широк
спектър от съвременните приложения изискват все по­
високи
скорости на информационната обработка, надхвърлящи
възможностите
на последователните компютри. За повишаването
на
компютърната производителност се използват два основни
подхода
: технологични подобрения и архитектурни иновации.
Усъвършенстването
на елементната база се ограничава от
скоростта
на светлината, законите на термодинамиката и високата
цена
на производството на процесори. Основният проблем при
съвременните
процесори се поражда от голямата разсейвана
мощност
и достигането на т.нар. “термална стена”. За
преодоляването
му водещи компютърни фирми като
Intel, IBM, Sun
Microsystems, AMD
предпочетоха използването на многоядрени
микропроцесори
при изграждането на настолни компютри и
сървъри
вместо създаването на микропроцесор с тактова честота
10 Ghz.
Следователно
съвременната стратегия за повишаване на
компютърната
производителност е използването на паралелизми.
Развитието
на архитектурата на процесорите през последното
десетилетие
се характеризира с устойчива тенденция за
оползотворяване
на паралелизми както на ниво инструкции (
ILP­
Instruction Level Parallelism),
така и на ниво нишки (
TLP­ Thread Level
Parallelism).
В резултат на архитектурните иновации, основани на
паралелизми
на ниво инструкции, се появиха суперскаларните
процесори
, които изпълняват повече от една инструкция за
машинен
цикъл. Използването на паралелизми на ниво нишки
доведе
до създаването на многоядрените процесори и
съответните
приложни програмни интерфейси, осигуряващи
ефективна
поддръжка на многонишковата обработка. За
постигането
на висока производителност съвременните
компютърни
специалисти трябва да разчитат основно на
създаването
на ефективно приложно паралелно програмно
осигуряване
, което максимално да използва паралелните апаратни
ресурси
на компютърната платформа.
Концепцията
за изграждане на паралелни компютърни
Този
учебен материал е публикуван от потребител в www.referati.org

платформи
с възможност за мащабиране широко се прилага в
университетите
, фирмите и организациите с цел създаването на
високопроизводителни
изчислителни системи при разумна цена.
Идеята
за клъстериране на наличните компютри в рамките на една
или
повече сгради и използването им като интегриран
изчислителен
ресурс е особено привлекателна и дава възможност
за
решаването на големи приложения за по­ малко време при
разумна
цена. Сега повече от половината от най­
високопроизводителните
компютри в света имат клъстерна
архитектура
.
Паралелната
информационна обработка има три основни аспекта:
• Системни
архитектури
• Паралелно
програмиране
• Паралелни
алгоритми и приложения
Комбинацията
от паралелното приложение и паралелната
компютърна

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

mm
форми добавя ново измерение към алгоритмичния синтез.
Един
от основните проблеми е да се разгледат взаимоотношенията
между
алго
ритмичното
и архитектурното пространство. Главната
цел
на паралелната обработка е да се получи максимална
производителност
и тази цел може да бъде постигната само ако се
анализира
архитектурният стил на паралелния компютър и се
определят
и изследват важните фактори, определящи
производителността
на паралелната система. Архитектурният стил
на
паралелната компютърна платформа определя съществено и
използвания
стил на паралелно програмиране.
Стратегиите
за синтез на паралелни алгоритми се различават
съществено
от традиционните процедури за алгоритмичен синтез
за
конвенционалните компютри. Проектантът има на
разположение
три алтернативи: да паралелизира съществуващ
последователен
алгоритъм (в този случай трябва да се осигури
алгоритмична
еквивалентност), да създаде нов паралелен
Този
учебен материал е публикуван от потребител в www.referati.org

алгоритъм
или да направи ефективна комбинация от
съществуващи
последователни и/или паралелни алгоритми за
решаването
на проблема. Критичният проблем при паралелната
информационна
обработка е интерфейсът между двата най важни
аспекта
­ архитектурата и алгоритъма.
Особено
голямо предизвикателство е паралелното решаване на
оптимизационни
проблеми, които не могат да се решат за
полиномно
време и полиномно мощни изчислителни ресурси.
Паралелните
еволюционни изчисления, основани на генетични
алгоритми
, осигуряват възможност за значително ускоряване и
получаването
на решения, близки до оптималното, и приемливо
време
. Освен това при паралелните генетични модели могат да
бъдат
използвани стратегии и средства за подобряване па
качеството
на решенията като миграция на хромози между
паралелните
еволюции и/или разнообразни паралелни форми на
генетичните
операции като селекция, кръстосване и мутация.
Паралелното
програмиране е по­сложен интелектуален процес от
последователното
програмиране, тъй като обхваща всички аспекти
на
последо
вателното
програмиране и освен това трябва да бъдат
решавани
нови про
блеми
и да бъдат посрещани нови
предизвикателства
. При последователното програмиране
съществува
само един базов модел ­ Фон Ноймановият модел
(
който се използва десетилетия без съществени модификации),
докато
при паралелното програмиране съществува голямо
разнообразие
от паралелни програмни модели и парадигми. Освен
това
средствата на програмните среди като компилатори, програми
за
настройка и профилиране са много по­развити при
последователното
програмиране. Те показват устойчивост при
мащабирането
по отношение на генерациите в компютърната
еволюция
. Проектантите на паралелно програмно осигуряване
трябва
да решават про
блеми
, които не са характерни за
последователното
програмиране, като не­детерминираност,
комуникация
, синхронизация, разделяне и разпределяне на
данните
, баланс на изчислителния товар, „мъртво" и „живо"
блокиране
, хазарти.
Проектирането
и имплементирането на паралелен софтуер
изисква
тясното взаимодействие между проектантите на
паралелни
алгоритми и системните архитекти. Паралелизмите
въвеждат
допълнителни параметри, които трябва да бъдат
Този
учебен материал е публикуван от потребител в www.referati.org

контролирани
и управлявани за подобряване и оп
тимизиране
на
изпълнението
на паралелните програми. За създаването на
висококачествени
и ефективни имплементации на паралелните
алгоритми
са необходими специфични средства за трасиране и
профилиране
на паралел
ната
програма, разпределението на
ресурсите
, съдържанието на паметта и структурите данни, между­
процесорните
комуникации, статичното и дина
мичното

разпределение
на процесите. Съществуват значителни трудности
при
пренасянето на паралелните програми от една паралелна
компютърна
платформа на друга поради зависимостта на
паралелната
програмна имплементация от системната
архитектура
.
Производителността
и ефективността на паралелната програма са
съществени
фактори при проектирането на паралелния софтуер.
Прогнозиране
и оценяване на производителността се налага да се
прави
на всеки от етаните при проектирането и имплементирането
от
фазата на първоначалния проект, през детайлното проектиране
и
кодиране до тестването и настройва
нето
на крайната паралелна
имплементация
.
1.4.
КОМПЮТЪРНИ КЛЪСТЕРИ

Компютърните
клъстери са най­популярният архитектурен
клас
при

изграждането
на високопроизводителни компютри или заместители
на
т
aкива
. Клъстерът представлява
колекция
от цели компютри (възли),
които физически
са свързани от високо производителна мрежа или
локална

мрежа
.
В
общия случай всеки възел представлява сървър, който е симетричен мултипроцесор,
работна
станция или персонален компютър. Всички
възли
на
клъстера
трябва да работят колективно като
един
интегриран
изчислител ен ресурс
. Допълнително отделните възли трябва да изпълняват
конвенционалната си
роля индивидуално за интерактивните потребители. В
компактните клъстери
всеки
възел
представлява цялостна работна станция без
някои
от
периферните
устройства (дисплей, клавиатура,
мишка
и др. Понякога такъв
възел се
нарича
работна
станция „без глава".
Възлите

се
свързват чрез

Ethernet, FDDI, Fiber­Channel или

ATM комутатор
. В
рамките
на възела мрежовият интерфейс е слабо

свързан
към
входио
/изходната шина.
Това

контрастира
с тясно свързания мрежов интерфейс на масивно
паралелните
процесори, който е свързан към шината на паметта на обработващия възел. Винаги има
локален
диск, който не е задължителен за възела на масивно паралелните процесори. Всеки възел се
управлява
от цялостна операционна система, докато при някои масивно паралелни процесори се използв