On choosing space-time mappings during automatic parallelization of loop nests with static control flow

Problems of affine scheduling and spatial distribution for programs composed of loop nests with static control flow are considered as multi-objective optimization problems with no uncertainty in context of data locality optimization. Presented method based on polyhedral model appliance computes space-time mapping to expose parallelism while minimizing data reuse latency in time domain and data reuse distance in space domain for each data dependence on the assumption of subjective preferences of the decision maker on optimization quality for each dependence. Subjective preferences are defined by weighting coefficients in linear form of scalarized multi-objective problem. Finding Pareto-optimal solution is reduced to solving of integer linear programming problem. The method allows to specify subjective preferences more precisely (notably for weakly parameterized programs or for programs with artificially de-emphasized parameterization during Just-In-Time compilation) in contradistinction to classic methods relying on lexicographic optimization such as Pluto. Application of the method is illustrated with parallelization of LU-decomposition algorithm. Parallel version of the algorithm obtained with presented method outperforms the result obtained with Pluto compiler.