Developing Data Redistribution Algorithms

Purpose

• Developing Communication Models that can represent the characteristics about each communication link and its bandwidth.
• Developing Data Redistribution Algorithms using AI techniques.
• Verifying Algorithms by using NOC SystemC Simulators.

Idea Sketch

• Idea.1.A (pdf)

Communication Patterns and Models

Parallel Prefix Sum

• ParaPrefix.1.A (pdf)
• MPI implementation (pdf)
• OpenMP implementation (pdf)
• CUDA implementation (pdf)

Redistribution Algorithms using a Generalized Circulant Matrix

Applying Sudoku Problems to Data Redistribution

Sudoku Codes in Haskell

from [ Haskell_programming_in_plain_view ]

• Sudoku Background (pdf)
• Bird's Implementation

- Specification (pdf)

- Rules (pdf)

- Pruning (pdf)

- Expanding (pdf)

Background

• Y. Ishikawa : "Efficient Collective Operations for Clusters in Long-and-Fast Networks"
• R. V. de Geijn : "Collective Communications on Architectures that Support Simultaneous Communications over Multiple Links"
• R. Rabenseifner : "Optimization of Collective Communication Operations in MPICH"

• NoC Simulator

- NIRGAM (SystemC)- University of Southampton, 2007

- OCCN (SystemC) - ST Microelectronics, 2005

- TOPAZ (C++) - University of Cantabria, 2012

- HNoCs (OMNeT++) - Technion, 2011

• MPI+NOC Literature to be surveyed.

• Y. W. Lim : "Efficient algorithms for block-cyclic redistribution of arrays", 1999

Circulant Matrix based redistribution (pdf)

go to [ Electrical_&_Computer_Engineering_Studies ]

* Idea.2.A (pdf) moved to CORDIC Hardware Implementations