This article studies the a nity scheduling problem in multicore computing systems, considering the minimization of communications and synchronizations. The problem consists in assigning a set of tasks to resources to minimize the overall execution time of the set of tasks and the execution time required to compute the schedule. A Multiobjective Iterated Local Search method is proposed to solve the studied a nity scheduling problem, which considers the di erent times required for communication and synchronization of tasks executing on di erent cores of a multicore computer. The experimental evaluation of the proposed scheduling method is performed over realistic instances of the scheduling problem, considering a set of common benchmark applications from the parallel scienti c computing eld, and a modern multicore platform from National Supercomputing Center, Uruguay. The main results indicate that the proposed multiobjective Iterated Local Search method improves up to 21.6% over the traditional scheduling techniques (a standard Round Robin and a Greedy scheduler)
Scheduling is a key problem on Heterogeneous Computing (HC) systems [
A nity scheduling [
Traditional scheduling problems are NP-hard, thus exact resolution techniques are only useful
to solve small problem instances (i.e., few tasks, few resources). Metaheuristics [
In this line of work, this article proposes a multiobjective metaheuristic approach to solve the assignment problem related to a nity scheduling in multicore NUMA systems. A Multiobjective Iterated Local Search (MILS) scheduler is introduced to improve tasks e ciency by minimizing communication/synchronization times and the e ective time required to compute the schedule. The experimental evaluation of the proposed method is presented for real parallel scienti c computing benchmark applications, considering di erent topologies and communication patterns, and also real multicore computing platforms. Results indicate that the proposed multiobjective Iterated Local Search method improves up to 21.6% over traditional scheduling techniques used as baseline for the comparison.
The mathematical model of the a nity scheduling problem to minimize communications and synchronizations in multicore computing systems (ASP-CS) considers the following elements: A multicore system with a set of cores N = fn1; : : : ; nag.
A set of tasks T = ft1; : : : ; tbg to be executed on the system.
A communication function C : T T ! N+, where C(ti; tj ) indicates the number of communications between two tasks ti and tj , 1 6 i 6 b, 1 6 j 6 b.
A synchronization function S : T T ! N+, where S(ti; tj ) indicates the number of synchronizations between two tasks ti and tj , 1 6 i 6 b, 1 6 j 6 b.
A communication cost function CC : N N ! R+, where CC(nh; nk) is the time required to communicate tasks executing in cores nh and nk, 1 6 h 6 a, 1 6 k 6 a.
A synchronization cost function SC : N N ! R+, where SC(nh; nk) is the time required to synchronize tasks executing in cores nh and nk, 1 6 h 6 a, 1 6 k 6 a.
The ASP-CS problem proposes nding a scheduling function f : T ! N to assign tasks to cores in the multicore system (f (ti) = nh indicates that task ti is assigned to execute on core nh, 1 6 i 6 b and 1 6 h 6 a), to minimize the total time demanded for communication and synchronizations between tasks (Eq. 1) and minimize the overall execution time to compute the schedule, in order to provide an accurate method to be applied in real time. The ASP-CS problem follows a non-preemptive model: each task is considered as an atomic processing unit, which cannot be divided nor interrupted.
X X C(ti; tj ) ti2T tj2T
CC(f (ti); f (tj )) + S(ti; tj )
SC(f (ti); f (tj )) (1)
ASP-CS is a NP-hard combinatorial optimization problem [
MILS is a metaheuristic method that extends the traditional local search by including a perturbation operator to escape from local optima and a multiobjective evaluation considering Pareto dominance.
Algorithm 1 presents a pseudocode of the proposed scheduler. The search starts from a randomly generated initial solution. MILS is an iterative method; in each iteration, the current candidate solution is perturbed and improved using a local search that involves di erent tasks movements, proved to be useful for HC scheduling [6]: random move, move to the least loaded resource, move from the most loaded resource and swap. The perturbation is a diversi cation operator, whose main goal is to provide MILS the capability of escaping from local optima. The acceptance criterion applies Pareto dominance to determine if the current solution is replaced by the best solution found in the neighborhood of the perturbed solution. The iterative process repeats until a given stopping criteria (e.g., a prede ned e ort stopping criterion or a stagnation detection) is met.
Algorithm 1 Schema of the proposed MILS sceduler.
1: s0 GenerateInitialSolution() 2: s LocalSearch(s0)
4: s0 Perturbation(s ) 5: s00 LocalSearch(s0) 6: s ParetoBased-AcceptanceCriterion(s ,s00) 7: until stop criterion is met
The proposed MILS aims at providing an e cient real-time scheduler for modern multiprocessors, which dynamically incorporates information about the processor architecture and also topological information about the application, provided by the user. The main features of the processor architecture (number of cores, topology, and organization) are obtained at runtime using the hwloc tool [7]. hwloc provides qualitative and quantitative information about the computing elements and the underlying architecture via an Application Programming Interface developed in the C language. Using runtime information allows the proposed scheduler to be integrated in modern Resource Management Systems for cluster and other High Performance Computing infrastructures.
The evaluation of the proposed scheduler was performed considering problem instances of three real scienti c computing applications with di erent communication patterns: Heat : A numerical analysis application describing the evolution of temperature in a bar. The application solves the di erential equation governing the heat transfer process applying a master/slave parallel model and domain decomposition. The communication pattern follows a at topology, where a master process sends data to a set of slaves processes for computation; slaves compute and send back the results to the master, which reduces the results. Slaves communicate with each other to deal with computations in the borders of the domain decomposition. The topology is described in Figure 1, where M is the master, Si are the slave processes, and communications costs are the labels of each edge. Work ow : Describes a generic work ow application, where data are distributed and processed by several independent tasks, dependencies between them, according to a speci c ow. No distinguished process controls the ow, but critical path determines the e ciency of the application. Communications and synchronizations are de ned according a levelbased synchronization pattern, as described in Figure 2. Blue rectangles represents synchronizations and the corresponding synchronization costs are marked in blue.
Quicksort : This sorting algorithm follows a topology with a hierarchical order de ned between tasks. Each task communicates exclusively with tasks in the nearest levels in the hierarchy. Synchronizations are performed between tasks in the same level. The topology is that of a tree, where communications are performed between parent and children and synchronizations are between siblings, as described in Figure 3. S2 80 4 4 2 2 2 2 2
Experiments were performed over a Intel Xeon Gold 6138 multicore server from National Supercomputing Center (Cluster-UY), Uruguay [8]. Cluster-UY is a relevant high performance computing platform in the Latin-American ecosystem for e-science, executing many large-scale scienti c applications that can take advantage of accurate scheduling to compute better results in reduced execution times [9]. The hardware architecture of the considered server is presented in Figure 4, as reported by the hwloc tool.
GH 12.8% 8.0% 3.6% 10.1% 6.7% 2.3% 10.8% 7.4% 3.2%
RR 21.6% 18.4%
8.4% 19.5% 12.4%
5.9%
GH 9.3% 2.0% 8.5% 1.5% 5.3% 8.2% 9.4% 8.3% 6.7%
RR 13.2%
9.7% 10.0%
7.8% 10.5%
8.9%
GH 7.7% 3.9% 3.2% 3.9% 4.3% 3.0% 7.3% 4.3% 3.7%
RR 16.4% 5.9% 5.4% 7.0% 8.3% 6.6%
Results on Table 1 demonstrate that the proposed MILS is able to compute accurate schedules regarding both execution time of the batch of tasks and the scheduler execution time. Improvements over the traditional RR heuristic were up to 21.6% when considering 64 tasks to be scheduled in a six-cores server. Improvements over GH were up to 12.8%. The best improvements were obtained for problem instances with the highest ratio of tasks per available core. Solutions computed by MILS clearly dominated GH, as reported in the dominance analysis presented in Figure 5 for a representative case study. MILS is able to better capture the main features of the underlying architecture and properly explore the search space of the problem. )%20 ( t n e em15 v o r p im10 e m i lt 5 a t o T 0
0
GH
RR best solutions
dominated by MILS GH
GH 1 2 3 4 Scheduler time (s)
This article addressed the a nity scheduling problem of parallel applications in multicore systems to minimize the execution time of a batch of tasks, considering communications and synchronizations between processes, and the execution time required to compute the schedule.
A MILS metaheuristic was proposed to solve the scheduling problem, including speci c Pareto-based local search operators and considering Pareto dominance as acceptance criterion for solutions found in the search. The experimental evaluation of the proposed MILS was performed over realistic instances of the scheduling problem, considering parallel scienti c applications with di erent communication/synchronization patterns and a modern multicore platform from National Supercomputing Center, Uruguay. The main results of the evaluation indicate that the proposed MILS is an e ective method for a nity scheduling, improving up to 21.6% over traditional scheduling techniques.
The main lines for future work are related to extend the evaluation of the proposed multiobjective scheduler, by considering other realistic applications and multicore architectures, and the use of automatic pro ling tool to characterize the considered applications. [6] Nesmachnow S, Cancela H and Alba E 2012 Applied Soft Computing 12 626{639 [7] Goglin B 2014 Managing the topology of heterogeneous cluster nodes with hardware locality (hwloc) High
Performance Computing & Simulation pp 74{81 [8] Nesmachnow S and Iturriaga S 2019 Cluster-UY: Collaborative Scienti c High Performance Computing in Uruguay Supercomputing Communications in Computer and Information Science (Springer International Publishing) pp 188{202 [9] Gitler I, Gomes A and Nesmachnow S 2020 Communications of the ACM 63 66{71 [10] Regueira D, Iturriaga S and Nesmachnow S 2017 Communication-aware a nity scheduling heuristics in multicore systems High Performance Computing Communications in Computer and Information Science (Springer International Publishing) pp 33{48