Premium
GbA: A graph‐based thread partition approach in speculative multithreading
Author(s) -
Li Yuxiang,
Zhao Yinliang,
Wu Qiangsheng
Publication year - 2017
Publication title -
concurrency and computation: practice and experience
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.309
H-Index - 67
eISSN - 1532-0634
pISSN - 1532-0626
DOI - 10.1002/cpe.4294
Subject(s) - computer science , thread (computing) , multithreading , parallel computing , partition (number theory) , simultaneous multithreading , graph partition , compiler , multi core processor , speculative multithreading , partition problem , graph , theoretical computer science , programming language , mathematics , combinatorics
Summary Speculative multithreading is an effective technique to automatically parallelize sequential programs. Conventional thread partition approaches primarily include heuristic rule–based (HR‐based) and machine learning–based. Heuristic rule–based approaches are effective to parallelize one type of programs and can seldom obtain the respective optimal partitions for different programs, and existing machine learning–based approaches usually use vector‐based characterization to represent a program, but easily ignore control information among basic blocks and partitions along other paths except the critical path. This paper proposes a novel graph‐based thread partition approach to overcome these 2 bottlenecks. Our approach characterizes programs with graphs, integrating feature and control informations, extracting good partition scheme successfully, and also applies a machine‐learning algorithm to predict partition for unseen programs. Prophet, which consists of an automatic parallelization compiler and a multicore simulator, evaluates the performance of multithreaded programs. Experiment results reveal that our approach delivers a maximum performance improvement of about 55.49% on an 8 core than HR‐based approach and a maximum 97.67% performance improvement over HR‐based partition for SPEC2000 benchmarks. This result suggests that graph‐based thread partition approach is effective for thread partition in speculative multithreading.