Minimum lock assignment: A method for exploiting concurrency among critical sections

Abstract. In this paper we propose a lock assignment technique to sim-plify the mutual exclusion enforcement in multithreaded programs. Pro-grammers are allowed to annotate the regions of code that are expected to be mutually exclusive as critical sections, without using explicit locks. The compiler then automatically infers an assignment of the min-imum number of locks to critical sections by solving the Minimum Lock Assignment (MLA) problem so as to enforce mutual exclusion without any loss of concurrency. We show that the MLA problem is NP-hard. We have proposed a heuristic to solve the MLA problem, and tested the optimality of the heuristic with the Integer Linear Programming (ILP) solver. We have also tested the efficiency of the heuristic using scientific applications, from which we obtain up to 30 % performance gain with respect to the programs in which all critical sections are controlled by a single lock.