A Concurrent Multi-Stealing Scheduler Model For Divide And Conquer Problems

Malaysian Journal of Computer Science

Lee Sai Peck¹  Alaa M. Al-Obaidi¹ 

关键词: Concurrency;    Multithreading;    Colored Petri Nets;    Divide and Conquer;    Matrix Multiplication;   

DOI  :  

学科分类：社会科学、人文和艺术（综合）

来源: University of Malaya * Faculty of Computer Science and Information Technology

【 摘 要 】

Multicorearchitecturehasdramaticallychangedthegeneraldirectionofsoftware developmentdedicatedfor personal computers. As such, it is important for software designers to keep pace with the evolving challenges that happen in the hardware side, for example in this context of multicore architecture, so that they can leverage on the advantagesofmulticoretechnologyasmuchaspossiblewhiledevelopingsoftware.Asoneofthewell-known techniques, Divide and Conquer has a natural adaptation with the multicore technology. The technique needs to be furtherdevelopedtofitintothisnewenvironment.Inthispaper,wepresentanewconcurrentmultithreaded ColoredPetriNetsmodelthatprovidesanewapproachforschedulingDivideandConquerproblemsona multicoreenvironment.Two newschedulershavebeendeveloped tocontrol theactionsof themodel.TheMulti Stealing Scheduler (MSS) has been designed to redistribute threads among the modelled cores. The MSS is general, scalableanditcanbeusedforanyDivideandConquerproblem.ThesecondscheduleristheLocalThreads Scheduler (LTS) that has the duty of threads creation and division inside each modelled core. In addition, the LTS introduces a new recursive method to provide the necessary information to multiply two matrices. Two main things havebeenachieved:First,workloadamongthemodelledcoresbecomeswellbalanced;second,thetechnique produces a high level of concurrency between the elements of the model, which greatly minimise the execution time.

【 授权许可】

Unknown