Charts and notes and working drafts preceding
the submission of “Network Topology Aware Scheduling of Collective
Communications” to ICT’03
This page is created for personal note-taking (working drafts cannot be
considered as definitive documents)
020214-liquidsched-fontszdiag [fm]
020225-liquidsched-fontszdiag [fm]
|
020314-deviation Comparison of the theoretical liquid throughput with the throughput of transfers carried out according to a liquid schedule [xls] |
020318-liquidsched-withminidiag [pdf], [fm]
020319-liquidsched [fm]
020403-skeletoncontent/
|
|
a1 percentage of skeleton transfers in 363 traffic patterns |
|
a2 percentage of skeleton transfers in 342 traffic patterns |
020408-liquidsched-searchspace [fm]
020408-searchspace/
020416-ratio1 [xls]
020416-ratio2 [xls]
|
|
a7 search space reductions achieved by three optimizations (skeleton: build first the skeleton patterns and then continue growing up the remaining transfers) [xls] |
020415-liquidsched [fm]
020418-liquid/
|
|
020418-520K-roundrobin Comparison of the theoretical liquid throughput with the throughput of transfers carried out according to round-robin schedules [xls] |
|
|
020418-liquidperf-onUTS Liquid throughput of 363 traffic patterns [xls] |
|
020418-optia2a-64p Liquid throughput and the median of 7 measured throughputs of transfers carried out according to liquid schedules [xls] |
|
|
020418-optia2a-64p Median of 7 measurements [xls] |
020424-liquidsched-graph [fm]
020502-graph/
|
a Graph of a traffic pattern: number of transfers (vertices) and the number of congested pairs (edges) |
020502-liquidsched [pdf], [fm]
020502-sc2002-topoaware [fm]
020503-sc2002-topoaware [pdf], [fm]
020513-c-prog-full-simultaneities-brelaz/
|
|
a1 [xls] |
|
|
a2 [xls] |
|
|
a3 [xls] |
|
|
a4 [xls] |
|
|
a5 [xls] |
|
|
a6 [xls] |
|
out1 skeleton [txt] out2 idle [txt] out3 blank [txt] out4 merge-sh [txt] out5 a [txt] a7 [xls] |
The following C programs are not implementations of the liquid schedule construction algorithm. These programs are used for comparing the liquid scheduling algorithm with the heuristic graph coloring algorithm (Daniel Brelaz) and for estimating the search space reductions achieved by the optimizations of the liquid schedule construction algorithms.
020905 ms visual cpp project [zip]
020905 only source c-and-h files [zip]
|
|
020515-chromaticity Loss in throughput due to excess of colors in the heuristic graph coloring algorithm |
020522-liquidsched [fm]
020826-liquidsched
[pdf], [fm]
020827-articles/
[Aggarwal94] Alok Aggarwal, Amotz Bar-Noy, Don Coppersmith, Rajiv Ramaswami, Baruch Schieber, Madhu Sudan, “Efficient Routing and Scheduling Algorithms for Optical Networks”
[Battiti99] Roberto Battiti, Alan A. Bertossi, Maurizzio A. Bonuccelli, “Assigning Codes in Wireless Networks: Bounds and Scaling Properties”, ACM/Baltzer Wireless Networks, Vol. 5, 1999, pp. 195-209
[Beauquier97] B. Beauquier, J.C. Bermond, L. Gargano, P. Hell, S. Pérennes, U. Vaccaro, “Graph Problems Arising from Wavelength-Routing in All-Optical Networks”, 2nd IEEE Workshop on Optics and Computer Science (WOCS, part of IPPS’97), IEEE Press, April 1997
[Caragiannis02] I.
[Jacunski98] Matt Jacunski, P. Sadayappan, D. K. Panda, “All-to-All Broadcast on Switch-Based Clusters of Workstations”
[Zhu98] Chenxi
Zhu, M. Scott Corson, “An Evolutionary-TDMA Scheduling Protocol (E-TDMA) for
|
|
020827-chromaticity-v1-throughput Increased time of collective communication due to the excess of the colors in the heuristic graph coloring algorithm [xls] |
020828-topoawareCorr28August02 [fm]
|
|
020902-chromaticity-v2-perfloss Throughput loss in the heuristic method compared with the liquid throughput [xls] |
020902-traffic-v2-perfloss-by-brelaz-alg [pdf], [fm]
020905-brelaz/
|
|
Coloring time of the Brelaz’s Dsatur algorithm 020905-brelaz [txt] 020905-out-brelaz-chrom-and-speed [txt] 020905-brelaz-algspeed [xls] |
020906-traffic-v3 [fm]
020906-traffic-v4 [fm]
020910-traffic-v5 [fm]
020910-traffic-v6 [fm]
020910-ict03-submitted-liquid-schedules [pdf], [fm]
020930-liquidsched [fm]
021003-liquidsched [fm]
021008-liquidsched [fm]
021022-liquid-schedules-camdraft [fm]
021023-liquid-schedules-camdraft [fm]
021025-liquid-schedules-camdraft [fm]
021028-manuscript-final-ict03-camera-ready [pdf], [fm]
030226-ict03-Presentation-v6 [pdf], [fm]
030301-ict03-liquidsched-lspweb [pdf]
030301-ict03-ieeexplore [pdf]
* * *