Profile
International Journal of Computer & Software Engineering Volume 2 (2017), Article ID 2:IJCSE-115, 12 pages
https://doi.org/10.15344/2456-4451/2017/115
Research Article
Optimizing the Cyclic K-conflict-free Shortest Path Problem in a Network-on-chip

Boureima Zerbo1, Marc Sevaux2 *, Andr'e Rossi3 and Jean-Charles Cr'eput4

1Universit´e de Ouagadougou, Burkina-Faso
2Universit´e de Bretagne-Sud –Lab-STICC, CNRS UMR 6285, Lorient, France
3Universit´e d’Angers, LERIA, Angers, France
4Universit´e de Technologie de Belfort-Montb´eliard, France
Prof. Marc Sevaux, Universit´e de Bretagne-Sud –Lab- STICC, CNRS UMR 6285, Lorient, France; E-mail: marc.sevaux@univ-ubs.fr
31 January 2017; 28 June 2017; 30 June 2017
Zerbo B, Sevaux M, Rossi A, Cr'eput JC (2017) Optimizing the Cyclic K-conflict-free Shortest Path Problem in a Network-on-chip. Int J Comput Softw Eng 2: 115. doi: https://doi.org/10.15344/2456-4451/2017/115

References

  1. DallyW, Towles B (2001) Route packets, not wires: On-chip interconnection networks. Proceedings of the 38th Design Automation Conference. View
  2. Benini L, Micheli G (2002) Networks on Chips: A New SoC Paradigm. Computer 35: 70-78. View
  3. Agarwal A, Iskander C, Shankar R (2009) Survey of network on chip (NoC) architectures and contributions. Journal of Engineering, Computing, and Architecture 3: 1-15. View
  4. Goossens K, van Meerbergen J, Peeters A, Wielage R (2002) Networks on Silicon: Combining Best-Effort and Guaranteed Services. Design, Automation and Test in Europe Conference and Exhibition, Proceedings, pp 423-425. View
  5. Cong J, Liu C, Reinman G (2010) ACES: application-specific cycle elimination and splitting for deadlock-free routing on irregular network-onchip. In: Proceedings of the 47th Design Automation Conference, DAC ’10, ACM New York, USA, pp 443-448. View
  6. Evain S, Diguet JP (2007) Efficient space-time noc path allocation based on mutual exclusion and prereservation. In: Proceedings of the 17th ACM Great Lakes symposium on VLSI, Italy. View
  7. Dafali R (2011) Conception des r´eseaux sur puce reconfigurables dynamiquement. Phd dissertation, University of South Brittany, France.
  8. Millberg M, Nilsson E, Thid R, Jantsch A (2004) Guaranteed bandwidth using looped containers in temporally disjoint networks within the Nostrum network on chip. In: Proceedings of the conference on Design, automation and test in Europe. View
  9. Marescaux T, Brick´e B, Debacker P, Nollet V, Corporaal H (2005) Dynamic time-slot allocation for QoS enabled networks on chip. In: 3rd Workshop on Embedded Systems for Real-Time Multimedia, pp 47-52. View
  10. Hansson A, Goossens K, Radulescu A (2007) A unified approach to constrained mapping and routing on network-on-chip architectures. In: CODES+ISSS’05 Proceedings of the 3rd IEEE/ACM/IFIP international conference on Hardware/software codesign and system synthesis, pp 75- 80. View
  11. Stefan R, Goossens K (2011) Enhancing the security of time-divisionmultiplexing networks-on-chip through the use of multipath routing. In: Proceedings of the 4th International Workshop on Network on Chip Architectures, ACM New York. View
  12. Ge F, Wu N (2010) Genetic algorithm based mapping and routing approach for network on chip architectures. Chinese journal of Electronics 19: 91-96.
  13. Lin CA, Hsin HK, Chang EJ,Wu AYA (2013) ACO-based fault-aware routing algorithm for networkon-chip systems. In: SIPS 2013 Proceedings, pp 342- 347. View
  14. Benmessaoud Gabis A, Koudil M (2016) NoC routing protocols-objectivebased classification. Journal of Systems Architecture 66: 14-32. View
  15. K¨ohler E, Langkau K, Skutella M (2002) Time-expanded graphs for flowdependent transit times. European Symposium on Algorithms 2461: 599- 611. View
  16. Kolliopoulos SG (2007) Edge-disjoint paths and unsplittable flow. In: T. F. Gonzalez (ed) Handbook of Approximation Algorithms and Metaheuristics, Chapman & Hall/CRC.
  17. Karp RM (1975) On the computational complexity of combinatorial problems. Networks 5: 45-68. View
  18. Lynch JF (1975) The equivalence of theorem proving and the interconnection problem. ACM SIGDA Newsletter 5: 31-36. View
  19. Gonzalez TF, Serena D (2004) Complexity of pairwise shortest path routing in the grid. Theoretical Computer Science 326: 155-185. View
  20. Desrochers M, Soumis F (1988) A generalized permanent labelling algorithm for the shortest path problem with time windows. INFOR 26: 191- 212. View
  21. M¨ohring RH, K¨ohler E, Gawrilow E, Stenzel B (2004) Conflict-free Realtime AGV Routing. Operations Research Proceedings, pp 18-24. View
  22. Ioachim I, G´elinas S, Soumis F, Desrosiers J (1998) A dynamic programming algorithm for the shortest path problem with time windows and linear node costs. Networks 31: 193-204. View
  23. Powell WB, Chen ZL (1998) A Generalized Threshold Algorithm for the Shortest Path Problem with Time Windows. In: DIMACS Series in Discrete Mathematics and Theoretical Computer Science. View
  24. Ford LR, Fulkerson DR (1958) Constructing maximal dynamic flows from static flows. Operations Research 6: 419-433. View
  25. Johnson DS, McGeoch LA (1997) The Traveling Salesman Problem: A Case Study in Local Optimization. View
  26. Schrimpf G, Schneider K, Stamm-Wilbrandt H, Dueck V (2000) Record Breaking Optimization Results Using the Ruin and Recreate Principle. J of Computational Physics 159: 139-171. View
  27. Pande PP, Grecu C, Ivanov A, Saleh R (2005) Performance Evaluation and Design Trade-Offs for Network-on-Chip Interconnect Architectures. IEEE Transaction on Computers 54: 1025-1040. View