PaRLSched C++ Library

PaRLSched is a C++ library for optimally scheduling parallel threads in a many-core platform using distributed reinforcement learning (and more specifically, perturbed learning automata). It explores recent advancements of game-theoretic learning techniques and reinforcement learning for asymptotically converging to efficient allocations. In particular, it exploits real-time measurements of the performances of the computing threads, and adaptively pins them to the available CPU/NUMA cores in order to increase their overall performance over time. Given the rather fast convergence achieved, the attained completion time in platforms with small number of CPU cores is reduced in comparison with the corresponding completion time of the Linux scheduler. This is probably expected since the standard Linux scheduler does not incorporate real-time measurements of the performance of the threads into its scheduling decisions. The development has been reported into a series of scientific papers, including

• G. Chasparis, M. Rossbory, “Efficient Dynamic Pinning of Parallelized Applications by Distributed Reinforcement Learning,” International Journal of Parallel Programming, vol 47(1), pp. 24-38, 2019.
• G. Chasparis, V. Janjic, M. Rossbory, and K. Hammond, “Learning-based Dynamic Pinning of Parallelized Applications in Many-Core Systems,” Euromicro PDP’19, Pavia, Italy, 2019.
• G. Chasparis, M. Rossbory, and V. Janjic, “Efficient Dynamic Pinning of Parallelized Applications by Reinforcement Learning with Applications,” LNCS 10417, Euro-Par 2017, pp. 1-13, 2017.

The implementation code has become available in the following git-hub repository.

The pattern over which the threads are defined and the computational tasks executed is subject to the user and does not constrain the applicability of the scheduler. Furthermore, the details and nature of these computational tasks could be different for each thread and can be defined by the user within the “src/thread_routine.h” header file which is also provided. The use-cases provided are described in the following paragraphs.

Ant Colony Optimization (ACO)

It is a metaheuristic used for solving NP-hard combinatorial optimization problems. In particular, we apply ACO to the Single Machine Total Weighed Tardiness Problem (SMTWP). Briefly, this is a scheduling problem of jobs that are characterized by varying processing times, deadlines and weights. The objective is to find the schedule that minimizes the total tardiness. Further information can be found in M. Dorigo and T. Stülze, “Ant Colony Optimization,” Scituate, MA, USA: Bradford Company, 2004.

Blackscholes (BLA)

It calculates, using differential equations, how the value of an option changes as the price of the underlying asset changes; parallel implementation calculates values for the number of options at the same time, assigning a thread to each option (or a group of options). If the options are equally divided between threads, this results in a regular (in terms of task sizes) parallel application. In practice similar calculations are used by financial houses to price 10-100 thousands of options. This use-case has been extracted from the Parsec Benchmark Suite.

Swaptions (SWA)

It uses the Heath-Jarrow-Morton (HJM) framework to price a portfolio of swaptions. The HJM framework describes how interest rates evolve for risk management and asset liability management. For further information, please check the following reference D. Heath, R. Jarrow, and A. Morton, “Bond pricing and the term structure of interest rates: A new methodologyfor contigent claims valuation,” Econometrica, vol. 60, no. 1, pp. 77-105, Jan. 1992. The application employs Monte-Carlo simulation to compute the prices. It is regular in terms of task sizes, with a low degree of communication between different threads. It has been extracted from the Parsec Benchmark Suite.