Title: Department of Computer Science Seminar
Date:  Wednesday, 12 March 2003
Time:  4:00 pm to 5:00 pm
Venue: Room N101, CSIT Building [108]


Title:   A New Scheme to Realize Crosstalk-free Permutations in
         Optical MINs with Vertical Stacking


Speaker: Prof. Hong Shen, Graduate School of Information
         Science,  Japan Advanced Institute of Science and
         Technology

Abstract:
  Vertical stacking is an attractive technique for constructing
  nonblocking multistage interconnection networks (MINs). In this
  talk, I will first introduce the problem of realizing permutations
  cross-talk free in optical MINs and the Euler-Split technique for
  cross-talk free decomposition of permutations. I will then present
  a new scheme for realizing permutations crosstalk-free in a class
  of optical MINs built on vertically stacked copies of Banyan network
  (VSB). The basic idea of our new scheme is to classify permutations
  into permutation classes such that all permutations in one class
  share the same crosstalk-free decomposition pattern. Each permutation
  class requires to run the based crosstalk-free decomposition algorithm
  only once and the obtained crosstalk-free decomposition pattern can
  then be applied to all permutations in the class. This allows
  crosstalk-free decomposition of all permutations to be realized in a
  more efficient way than previously. It has been shown that the number
  of permutations in a permutation class is huge, enabling the average
  time complexity of the new scheme to realize a permutation crosstalk-
  free in an N x N VSB to be reduced to O(N) from previously O(NlogN).


Biography:
  Hong Shen is Professor and Chair of Computer Networks Laboratory
  in the Graduate School of Information Science, Japan Advanced Institute
  of Science and Technology (JAIST). Prior to joining JAIST, he was
  Professor in Griffith University, Australia. Prof. Shen has published
  over 140 technical papers on algorithms, parallel and distributed
  computing, networking, parallel databases and data mining. He has
  served as an editor of Parallel and Distributed Computing Practice,
  associate editor of International Journal of Parallel and Distributed
  Systems and Networks, editorial-board member of Parallel Algorithms
  and Applications, International Journal of Computer Mathematics and
  Journal of Supercomputing, and chaired various international
  conferences.


URL: http://cs.anu.edu.au/lib/seminars/seminars03/dept20030312