Developing Data Redistribution Algorithms

## Purpose

[edit | edit source]

* 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

[edit | edit source]

* Idea.1.A (pdf)

## Communication Patterns and Models

[edit | edit source]

### Parallel Prefix Sum

[edit | edit source]

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

### FFT

[edit | edit source]

## Redistribution Algorithms using a Generalized Circulant Matrix

[edit | edit source]

### Applying Sudoku Problems to Data Redistribution

[edit | edit source]

#### Sudoku Codes in Haskell

[edit | edit source]

from [ Haskell_programming_in_plain_view ]

* Sudoku Background (pdf)
* Bird's Implementation

\- Specification (pdf)
\- Rules (pdf)
\- Pruning (pdf)
\- Expanding (pdf)

#### Sudoku Codes in Prolog

[edit | edit source]

### Finding relationship with other algorithms

[edit | edit source]

#### FFT Algorithms using a Tensor Product

[edit | edit source]

#### FFT Algorithms using a Mixed Radix

[edit | edit source]

## Background

[edit | edit source]

* 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