Науковий вісник НГУ

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

• 
• 

Рейтинг користувача:  / 0

ГіршийКращий 

Деталі

Категорія: Інформаційні технології, системний аналіз та керування

Останнє оновлення: 03 жовтня 2016

Опубліковано: 03 жовтня 2016

Перегляди: 3789

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.

04_2016_Xiaohong
2016-09-26  288.33 KB  838

• < Попередня