Soluções de alto desempenho para a Ordenação Segmentada de Vetores e o Escalonamento de Tarefas

Abstract

Heterogeneous Computing Scheduling Problem (HCSP) consists of distribuiting the tasks between the available machines in the environment. Minmin heuristics have a good solution for this problem and can be very fast, compared with others for the same purpose. This work presents min-min implementations for the task scheduling problem in CPUs, and one implementation of the knapsack problem to reorder kernels in GPU. Before that, these two implementations were merged to solve the kernels scheduling problem in multiples GPUs. The most efficient algorithm for the min-min heuristic consists of solving the segmented sorting problem of an array. In this way, it was also realized a study about the existing segmented sorting implementations, and the new one suggested. The scheduling studies were realized in real development environments, and simulated environments of cloud computing, like the frameworks Cloudsim and GPUCloudsim. Results showed that heuristics, like min-min, can improve resource utilization on these tested environments.