Benchmarking: SUN High Performance Computing MPI versus MPICH on two applications

Saleh Elmohamed, Roman Markowski, and Geoffrey Fox

Northeast Parallel Architectures Center Syracuse University, Syracuse, NY 13244

{saleh, roman, gcf}@npac.syr.edu

January 10, 1998

ABSTRACT

1 Introduction

... ...

2 The Timetabling Problem

... ...

3 Mean-Field Annealing

... ...

4 The Rule-Based System

... ...

5 Simulated Annealing

... ...

5.1 Timetabling Using the Annealing Algorithm

... ...

5.2 The Annealing Schedules

... ...

5.3 The Choice of Moves

... ...

6 Experimental Results

... ...

7 Conclusions

... ...

Acknowledgments

First Semester Second Semester Third Semester
Rooms  509  509  120
Classes  3839  3590  687
Professors  1190  1200  334
Students  13653  13653  2600
Buildings  43  43  11
Schools/Colleges  20  21  17
Departments/  143  141  108

Course Prefix

Areas of Study (majors)  200  200  200

Table 1: Size of the data set for each of the three semesters.

Academic  sparseness
Time Period  ratio
First Semester  0.50
Second Semester  0.53
Third Semester  0.62

Table 2: The sparseness ratios of the problem for the data sets for each of the three semesters. Lower values indicate a harder problem.

Academic  Algorithm  Scheduled highest  lowest
Time Period  (average) Scheduled Scheduled
%  %  %
First Semester  SA (geometric)  65.00  67.50  56.80
SA (adaptive)  67.80  70.15  61.20
SA (cost-based)  70.20  72.28  68.80
ES  76.65  76.65  76.65
MFA  65.60  71.00  61.00
Second Semester SA (geometric)  65.65  68.00  57.10
SA (adaptive)  68.50  70.10  60.77
SA (cost-based)  75.14  77.68  70.82
ES  79.00  79.00  79.00
MFA  67.20  75.00  65.00
Third Semester SA (geometric)  83.10  86.44  68.50
SA (adaptive)  85.80  89.00  70.75
SA (cost-based)  91.20  95.18  85.00
ES  96.80  96.80  96.80
MFA  88.00  95.00  82.00

Table 3: Percentage of classes scheduled using the different methods. The averages and highest and lowest values were obtained using 10 independent runs for simulated annealing (SA) and mean-field annealing (MFA). The expert system (ES) is deterministic so the results are from a single run. No preprocessor was used with the three methods.

Academic  Algorithm  Scheduled highest  lowest
Time Period  (average) Scheduled Scheduled
%  %  %
First Semester  SA (geometric)  93.90  95.12  85.20
SA (adaptive)  98.80  99.20  95.00
SA (cost-based)  100.0  100.0  100.0
Second Semester SA (geometric)  95.00  98.95  89.40
SA (adaptive)  99.00  99.50  98.50
SA (cost-based)  100.0  100.0  100.0
Third Semester SA (geometric)  97.60  98.88  90.90
SA (adaptive)  100.0  100.0  100.0
SA (cost-based)  100.0  100.0  100.0

Table 4: Percentage of scheduled classes, averaged over 10 runs of the same initial temperature and other parameters, for three terms using simulated annealing with an expert system as preprocessor.

Figure 1: Runs vs. their runtimes. Figure 2: Runs vs. their runtimes.

Figure 3: Runs vs. their runtimes. Figure 4: Runs vs. their runtimes.