Controlling the correlation of cost matrices to assess scheduling algorithm performance on heterogeneous platforms. (14th June 2017)

• Record Type: Journal Article
• Authors: Canon, L.‐C.; Héam, P.‐C.; Philippe, L.
• Other Names: Lengauer Christian guestEditor.; Bougé Luc guestEditor.; Trystram Denis guestEditor.; Balaji Pavan guestEditor.; Leung Kai‐Cheung guestEditor.
• Is Part Of: Concurrency and computation. Volume 29:Number 15(2017)
• Page Start: n/a
• Page End: n/a
• Publication Date: 2017-06-14
• Subjects: correlation -- cost matrix -- measure -- parallelism -- scheduling -- unrelated; Parallel processing (Electronic computers) -- Periodicals; Parallel computers -- Periodicals; 004.35
• DOI: 10.1002/cpe.4185
• Languages: English
• ISSNs: 1532-0626

Abstract

Summary: Bias in the performance evaluation of scheduling heuristics has been shown to undermine the scope of existing studies. Improving the assessment step leads to stronger scientific claims when validating new optimization strategies. This article considers the problem of allocating independent tasks to unrelated machines such as to minimize the maximum completion time. Testing heuristics for this problem requires the generation of cost matrices that specify the execution time of each task on each machine. Numerous studies showed that the task and machine heterogeneities belong to the properties impacting heuristics performance the most. This study focuses on orthogonal properties, the average correlations between each pair of rows and each pair of columns, which measure the proximity with uniform instances. Cost matrices generated with 2 distinct novel generation methods show the effect of these correlations on the performance of several heuristics from the literature. In particular, EFT performance depends on whether the tasks are more correlated than the machines and HLPT performs the best when both correlations are close to one.