Developing Data Redistribution Algorithms

From Wikiversity
Jump to navigation Jump to search

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]

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