A Parallel Scanner for the Concurrent Execution of Lexical Analyzer Tasks on Multi-Core Machines using Dynamic Task Allocation Algorithm

Abstract

Purpose: Massive multi-core architecture is rapidly becoming the standard in digital technology due to its high and parallel computational capability and performance benefits. To fully utilize the technological capabilities of multi-core systems, system software such as compilers should be re-engineered for parallel processing. Several important contributions have been made in the past to enhance the efficiency of the lexical analysis process by leveraging the innate parallel processing capability of multi-core computers. This trend of implementation shows that a parallel lexical analyzer tends to perform lexing tasks better than a conventional sequential lexical analyzer. This article discusses the way of making the tasks in parallel during the scanning of source program in the phase of lexical analysis. The objective of this study is to explore how to perform lexical analysis in parallel. On multi-core processors, multiple processes of the lexical analyzer program can run concurrently to scan multiple lines in the input stream in parallel for token detection. This is done by allocating tasks line-by-line to the core which is not engaged yet.

Design/Methodology/Approach: Developing a theoretical and experimental approach for parallelizing the lexical scanning process on a multi-core system.

Findings/Result: According to the theoretical and experimental results, the proposed methodology significantly outperforms the sequential approach in terms of tokenization. It considerably reduces the time required for lexical analysis during the compilation process. The result establishes unequivocally that the parallel lexical analyzer's performance should scale linearly with the number of cores. It is clearly observed that the speedup is expected to increase further if the number of CPU cores increases. This enhancement would speed up the compilation process even more.

Originality/Value: A dynamic task allocation algorithm is developed for the concurrent execution of a lexical analyzer task on multi-core systems.

Paper Type: Experimental Research.