Supporting irregular and dynamic computations in data parallel languages

摘要: Data parallel languages support a single instruction flow; the parallelism is expressed at the instruction level. Actually, data parallel languages have chosen arrays to support the parallelism. This regular data structure allows a natural development of regular parallel algorithms. The implementation of irregular algorithms necessitates a programming effort to project the irregular data structures onto regular structures. In this article we present the different techniques used to manage the irregularity in data parallel languages. Each of them will be illustrated with standard or experimental data parallel language constructions.