|
eaDonNTU, Donetsk >
Научные труды ДонНТУ >
Серія: Інформатика, кібернетика та обчислювальна техніка >
Випуск 2 (18) >
Пожалуйста, используйте этот идентификатор, чтобы цитировать или ссылаться на этот ресурс:
http://ea.donntu.ru/handle/123456789/29931
|
| Название: | Оптимизация вычислительного процесса на многоядерной системе с использованием алгоритма искусственной пчелиной колонии |
| Другие названия: | Оптимізація обчислювального процесу на багатоядерній системі з використанням алгоритму штучної бджолиної колонії
Scheduling optimization in multicore system using artificial bee colony algorithm |
| Авторы: | Иванов, Ю.А.
Іванов, Ю.О.
Ivanov, Y.O. |
| Ключевые слова: | обчислювальний процес
метаеврестика
дискретна оптимізація
алгоритм штучної бджолиної колонії
вычислительный процесс
метаэвристика
дискретная оптимизация
алгоритм искусственной пчелиной колонии
computational process
metaheuristic
discrete optimization
artificial bee colony algorithm |
| Дата публикации: | 2013 |
| Издатель: | ДонНТУ |
| Библиографическое описание: | Наукові праці Донецького національного технічного університету. Серія: Інформатика, кібернетика та обчислювальна техніка : збірник статей. Вип.2 (18) / ДВНЗ "ДонНТУ" ; редкол.: О.Є. Башков (голов. ред.) та ін. - Донецьк : ДонНТУ, 2013. |
| Аннотация: | В статье рассмотрена задача разработки расписаний для эффективного управления процессом моделирования разночастотных динамических объектов в режиме реального времени на многоядерной платформе. Методами математического программирования данная
задача классифицирована как смешанная нелинейная целочисленная. В работе было предложено решение с использованием метавэвристического алгоритма искусственной пчелиной колони, адаптированного для поставленной дискретной задачи оптимизации. Предложен подход для инициализации начального состояния роя, как решение задачи о камнях с использованием жадного алгоритма. Для рассмотренных наборов входных данных определен оптимальный состав популяции в алгоритме. Выполненная оценка работы и надежности алгоритма показала возможность применимости и высокий уровень его эффективности при решении задачи разработки расписания. |
| Описание: | In this paper job-shop model for multicore platform was considered. The aim of the work is determination of model parameters and use them to develop schedule for hard real-time simulation. Relations in the model are set
to achieve optimal control for dynamic systems including significantly different object frequencies. The model that describes computational process is complex and has several strict restrictions. In terms of mathematical programming the task is classified as a mixed integer nonlinear problem (MINLP). Given problem is multi-objective and has multiple extremas. That means finding a relative minimum is very complex for this task. Well known methods were considered: simplex method, simulated annealing, genetic algorithm, ant colony optimization and the artificial bee colony. Metaheuristic artificial bee colony algorithm was proposed for solving. This
algorithm has been adapted for the solution of discrete optimization problem. In the paper a new approach was proposed to initialize the initial state of the swarm. Its value was determined as a solution of the bin packing problem using a greedy algorithm. In the worst case random initialization of a particular task may not give a feasible solutions that would satisfy the constraints posed. In addition a further bees movement to random positions also may not bring success. Therefore, as an initial value were proposed uniform basic task flow distributions across multiple cores to initialize bees’ positions in the work. With this formulation, we achieved the goal of the minimum value of the load on each the core. Also this solution allows getting an optimal value of the objective function on the first step of the algorithm. The optimal bee population for algorithm was defined for the known data sets. Experiment showed that algorithm is less sensitive to increase number of threads in simulation problem. In a case when required a schedule for specialized computer systems with more cores than the standard should be adjusted in the parameters of the algorithm to increase the performance and its accuracy. The reliability and feasibility of the algorithm were estimated for input test sequences. Test runs of algorithm demo nstrated
its applicability and high efficiency schedules as a result. |
| URI: | http://ea.donntu.org/handle/123456789/29931 |
| Располагается в коллекциях: | Випуск 2 (18)
|
Все ресурсы в архиве электронных ресурсов защищены авторским правом, все права сохранены.
|
