Dependence-Free Structured Decomposition of Group-Based Index Spaces

. Structured, dependence-free decomposition of aggregate data objects can be regarded as a generalized form of classical array alignment and addresses the problem of finding the maximum amount of independent computation on nonconnected data sets. The paper presents a unified concept for modelling both data spaces and affine dependence relations with the help of group theory. This approach allows us to treat alignment at a very high level of abstraction exploiting results of computational algebra. Contents 1 Introduction 4 2 Shift-Invariant Data and Dependence Structures 5 3 Index Spaces and Group Theory 6 3.1 Group-Based Index Spaces 7 3.2 Group-Based Dependence Relations 8 3.3 Fibre Spaces 8 4 The Alignment Process 9 5 Transformation Steps 10 5.1 From Bundle to Fibre Space 12 5.2 Eliminating Shifts 14 5.3 Transitive Closure 15 5.4 Factor Classes 16 6 Computational Aspects 17 7 Results and Open Problems 17 References 4 1 Introduction Exploiting data access locality is a key pr..