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

Рейтинг користувача:  / 0
ГіршийКращий 

Authors:

Сяохун Кун, Хенаньський інститут науки та технологій, Сіньсян, Китай

Жуйхуа Лі, Хенаньський інститут науки та технологій, Сіньсян, Китай

Яньцюнь Чжан, Хенаньський інститут науки та технологій, Сіньсян, Китай

Abstract:

Мета. Декілька процесорів можуть бути об’єднані разом у багатоядерній платформі й мати справу з багатомасштабними науковими проблемами із-за надлишку обчислень і обширного розпаралелювання. Ця робота, в основному, направлена на вирішення проблеми багатозадачного планування на цій платформі зі спільною пам’яттю й каналом зв’язку.

Методика. Як правило, інтенсивне обчислення завдання порціонується у крупні підзадачі так, що завдання виконуються паралельно (одночасно) для підвищення продуктивності обчислень. Запропонований алгоритм використовує програмування в обмеженнях для знаходження відповідного рішення та використовує локальний пошук для покращення виявлення рішення й прискорення процесу.

Результати. Спільне використання різних наявних ресурсів, багатопроцесорне планерування є складним комбінаторним завданням оптимізації та проблемою обмежених ресурсів. Досліджено, як отримати раціональне рішення або субоптимальне рішення в короткий період часу. У той же час, досліджені завдання з різними характеристиками, аби знайти, як характеристики додатків впливають на питому мету платформи.

Наукова новизна. Коли завдання призначені різним процесорам, мають бути розглянуті різні обмеження ресурсів, у тому числі зберігання даних, обчислювальна вартість, пріоритетність завдань і вартість зв’язків між процесорами. Розглядається гібридний алгоритм, заснований на пошуку із заборонами, з метою оптимізації часу завершення додатків, задовольняючи вказаним обмеженням.

Практична значимість. Алгоритм реалізований у середовищі IBM ILOG CPLEX Optimization Studio environment і дає кращі результати в порівнянні з іншими алгоритмами. Пропонований алгоритм є ефективною стратегією, і ця методика дозволяє підвищити ефективність пошуку й продуктивність для вирішення проблеми багатопроцесорного планування.

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

1. Davis, R.I. and Burns, A., 2011. A survey of hard real-time scheduling for multiprocessor systems. ACM Computing Surveys, Vol. 43, No. 4, pp. 1–44.

2. IBM Corporation, 2010. Cell Broadband Engine Programming Handbook, http://www-01.ibm.com/ chips/techlib/techlib.nsf/techdocs9F820A5FFA3ECE8C8725716A0062585F.

3. Benini, L., Lombardi, M., Milano, M. and Ruggiero, M., 2008. Optimal resource allocation and scheduling for the CELL BE platform. Annals of Operations Research, Vol. 184, No. 1, pp. 51–77.

4. Leila, I. and Driss, G., 2011. Performance Evaluation of Convolution on the Cell Broadband Engine Processor. IEEE Transactions on Parallel and Distributed Systems, Vol. 22, No. 2, pp. 337–351.

5. Edis, E.B. and Oguz, C., 2012. Parallel machine scheduling with flexible resources. Computers & Industrial Engineering, Vol. 63, No. 2, pp. 433–447.

6. Heinz, S., Ku, W.Y. and Beck, J. C., 2013. Recent Improvements Using Constraint Integer Programming for Resource Allocation and Scheduling. In: Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems. 10th International Conference, CPAIOR 2013, Yorktown Heights, NY, USA, May 18–22, 2013.

7. IBM Corporation, 2011. IBM ILOG CPLEX Optimization Studio CPLEX User’s Manual v12.4.

8. Canon, L.C. and Jeannot, E., 2009. Precise Evaluation of the Efficiency and the Robustness of Stochastic DAG Schedules. Research Report. Research Report RR-6895, INRIA.

9. Thevenin, S., Zufferey, N. and Widmer, M., 2013. Tabu search for a single machine scheduling problem with discretely controllable release dates. In: Slovenian Society Informatika, 12th International Symposium on Operational Research SOR’13 in Slovenia. Dolenjske Toplice, September 25–27, 2013. Slovenian Society Informatika – Section for Operational Research, Ljubljana, Slovenia.

Files:
04_2016_Xiaohong
Date 2016-09-26 Filesize 288.33 KB Download 678

Відвідувачі

6203019
Сьогодні
За місяць
Всього
1249
29696
6203019

Гостьова книга

Якщо у вас є питання, побажання або пропозиції, ви можете написати їх у нашій «Гостьовій книзі»

Реєстраційні дані

ISSN (print) 2071-2227,
ISSN (online) 2223-2362.
Журнал зареєстровано у Міністерстві юстиції України.
Реєстраційний номер КВ № 17742-6592ПР від 27.04.2011.

Контакти

49005, м. Дніпро, пр. Д. Яворницького, 19, корп. 3, к. 24 а
Тел.: +38 (056) 746 32 79.
e-mail: Ця електронна адреса захищена від спам-ботів. вам потрібно увімкнути JavaScript, щоб побачити її.
Ви тут: Головна Архів журналу за випусками 2016 Зміст №4 2016 Інформаційні технології, системний аналіз та керування Планування задач, що стоять перед багатопроцесорною платформою, з використанням програмування в обмеженнях і методу пошуку із заборонами