Лабораторна робота № 8

Мета роботи – вибір оптимального способу планування обчислень на заданій ПКС з урахуванням її параметрів.

Вхідні дані – результати шести алгоритмів планування, отриманих у результаті виконання лабораторних робіт №2-7.

Завдання роботи - порівняти шість реалізованих алгоритмів планування з точки зору їх ефективності. Порівняння необхідно виконувати на множині згенерованих випадкових графів задач. Для аналізу роботи алгоритмів використовувати наступні показники ефективності:

1. Коефіцієнт прискорення , де Т₁ – час виконання задачі на одному процесорі, Т_п - час виконання задачі на заданій КС.

2. Коефіцієнт ефективності системи ,

де К_пр- коефіцієнт прискорення, N – кількість процесорів КС.

3. Коефіцієнт ефективності алгоритму планування ,

де Т_кр – критичний час (теоретичний мінімум) виконання задачі на заданій КС.

Для виконання даної роботи необхідно задати наступні параметри в меню «Статистика»:

• мінімальну кількість вершин в графі задач;

• максимальну кількість вершин в графі задач;

• крок нарощування кількості вершин;

• початкова зв’язність згенерованої задачі;

• кінцева зв’язність згенерованої задачі;

• крок нарощування зв’язності;

• мінімальна вага вершин у графі задачі;

• максимальна вага вершин у графі задачі;

• кількість графів задач для статистики.

Список літератури

1. Трахтенгерц Э.А. Программное обеспечение параллельных процессов.- М.: Наука, 1987.- 356 с.

2. G. Loutsky, O. Rusanova Scheduling Problems on the Parallel and Distributed Systems - an Overwiew,“Computer Systems and Networks: designing, application, utilization”.- Poland, Rzeszow, 2000, tom 1, pp.101-105(Engl).

3. СуперЭВМ. Аппаратная и программная реализация. Под ред. С.Фернбаха.-М.:Радио и связь, 1991.- 320 с.

4. Барский А.Б. Параллельные процессы в вычислительных системах. Планирование и организация.-М.:Радио и связь, 1990.- 256 с.

5. Дж.Ортега Введение в параллельные и векторные методы решения линейных систем.-М.:Мир, 1991.-367 с.

6. Корнеев В.В. Параллельные вычислительные системы.-М:Мир, 1999.

7. Hesham El-Rewini, Ted G.Lewis. Distributed and Parallel Computing.-Manning Publications Co., 1997.-447 p.

8. V.Kumar, A.Grama, A.Gupta, G.Karypis. Introduction to Parallel Computing. Design and Analysis of Algorithms.- Benjamin/Cummings Pub.Co,1995.-597 р.

9. Русанова О.В., Ярох Ю.Н. Планирование вычислений в гетерогенных кластерных системах. Вісник НТУУ”КПИ”.Сер. Інформатика, управління та обчислювальна техніка. - 2011. Випуск 54. - С.155 –163.

10. Technical Report No. 2006-504 Scheduling Algorithms for Grid Computing: State of the Art and Open Problems. Fangpeng Dong and Selim G. Akl. School of Computing,Queen’s University Kingston, Ontario January 2006.

11. D.B.Skillicorn,Jonathan M.D.Hill, W.F.McCOLL. Questions and Answers about BSP. Scientific Programming, Vol.6, pp.249-274 (1997).

12. Бехтеяров С.Д., Дудников Е.Е., Евсеев М.Ю. транспьютерная технология.-М.:Радио и связь, 1993.-304 с.

13. Кейлингерт П. Элементы операционных систем.-М.:Мир,1985.-295 с.

14. Watson P., Robinson E.H. The Hardware Architecture of the ICL Goldrush MegaServer.Ungenuity. The ICL Technical Journal,1995.10(2): p.206-219.

15. Kevin Hao Liu. Performance Study on Optimal Processor Assignment in Parallel Relational Databases. Proceeding of ICS97, Vienna, Austria,1997, p.84-91.

16. Rusanova O., Korochkin A. Scheduling Problems for Parallel and Distributed Systems. – Proceedings of SIGAda’99 Conference; American Computer Machinery, USA, 1999. ( Engl).

17. Кулаков Ю.А.,Русанова О.В., Шевело А.П. Иерархический способ планирования для GRID Вісник НТУУ”КПИ”.Сер. Інформатика, управління та обчислювальна техніка. - 2009. Випуск 51. - С.57 – 66