An approach to modelling and simulating multithreaded schedulers for divide and conquer problems on multicore architecture / Alaa Mohammed Ali Wadi Al-Obaidi

• Main Author: Alaa Mohammed, Ali Wadi Al-Obaidi
• Format: Thesis
• Published: 2016
• Subjects: Q Science (General); QA76 Computer software
• Online Access: http://studentsrepo.um.edu.my/6688/4/alaa.pdf; http://studentsrepo.um.edu.my/6688/

The continuous increase in the number of cores and software size causes a distinct problem in the software world that utilizes multicore architecture. This problem is represented by the optimal use of the new technology and how this is reflected in software development. In the core of the problem, there are two main issues that must be considered. First, the partitioning of the workload of a problem at runtime so that the resultant workload partitions can be processed concurrently. Second, the dynamic balance of the workload that is generated by these partitions to be distributed among the cores. This matter is highly important because it addresses the problem of idle cores. In order to handle the problem of idle cores, this thesis adopts the work-stealing technique which has been successfully applied in multiprocessor systems to provide a workload balance between the multiprocessor systems by allowing the idle processors to work individually to steal part of the workload of the non-idle processors at run time so that the system can be balanced. However, as the number of cores increases, which may reach several hundred in the near future; it will be time consuming to allow each core to individually search for a non-idle core to steal part of its workload since the searching process in the existing work-stealing techniques is done randomly. This causes frequent failure especially when the workload is low and many cores are in an idle situation. This thesis proposes an approach to partition Divide and Conquer algorithms into workload partitions at run time so that they can be executed concurrently on a scaled multicore architecture. Therefore, the researcher proposes several problem oriented mechanisms to partition the workload. In addition, the researcher proposes a modification to the work-stealing technique by imposing a centralized control over the stealing process rather than allowing each core to work individually. Several rebalancing strategies are proposed to suit the conditions of the cores. To achieve these goals, the researcher designs scaled concurrent models that work under the principle of iv multithreaded scheduling. Two types of schedulers are proposed. The first type is responsible for creating, dividing, and manipulating the threads of the Divide and Conquer algorithms. The second type of schedulers is for balancing the threads using different rebalancing strategies. The researcher uses Colored Petri Nets as language of modelling and Colored Petri Nets Tool as the software that creates, simulates, and validates the models. The results of simulation models show a high efficiency in dealing with Divide and Conquer algorithms. The proposed concurrent models are scalable in terms of number of cores and problem size. The models can be easily expanded by adding more cores which influence effectively on the models’ performance. In other words, the results indicate that adding more cores minimizes the number of steps required to complete the simulation process of the models. In addition, the models show a high flexibility in dealing with various problem sizes, and maintain the integrity of results even when problem size is highly increased.