Xfor: Semantics and Performance

This paper introduces a new programming control structure called "xfor" as an extension of the classical "for" construct in C. It is designed to help one programmer to improve data locality on multi-core architectures by allowing him to express the schedule of instructions in an abstract way. This schedule is defined geometrically by mapping the iteration domains relatively to each other onto a unique referential by using specific parameters called grain and offset. A semantic framework is presented which associates a precise meaning with this syntactic construct and serves as a base for applying reliable xfor code transformations and programming strategies. These issues are illustrated with the Red-Black algorithm. Performance measurements carried out with benchmarking programs rewritten by using the xfor construct show significant execution times speed-ups