Stallmann, Brglez, Ghosh: Software Execution

Generation of experimental data, execution of heuristics, and formatting of results is accomplished by scripts in the three scripts_* directories. All scripts are designed to be executed in the directory that contains them, and, to avoid naming conflicts, have names prefixed with sbg_. They also all access information in the data directory, which is root_directory/data by default but can be changed by setting the DATA_DIRECTORY environment variable. Most of the scripts also assume that the bin directory specified during installation is in the current path -- if not, this can be remedied by setting the environment variable PROGRAM_DIRECTORY prior to execution of the script. All except one of the scripts uses csh; the exception is the perl script sbg_gen_abd in scripts_generate.

The index files in scripts_generate, scripts_execute, and scripts_evaluate give more detailed instructions for the appropriate scripts.

The actual programs that appear in the bin directory after installation are listed below. All programs and scripts print usage messages when invoked with no command-line arguments.

• Generators
  • sbg_comm_graph rank type base_name - creates a butterfly, hypercube, or grid (type is one of bfly, hcube, grid) of the given rank, writes the graph description in file base_name.dot, and a canonical order in file base_name.dot.ORD.
  • sbg_random_graph <options> - creates a random bipartite graph based on settings of various options. More detailed information is available.
  • sbg_scramble dot_file N seed_file verbose update_seed - creates N scrambled isomorphs of the graph in the dot_file using the seed_file to initialize the rand48 generator; verbose and update_seed are boolean (0 or 1), and determine whether detailed information about each scrambling is written (verbose) and whether the seed file is updated after scrambling to reflect the new position in the random stream.
  • sbg_vlsi_graph rank type base_name - same as sbg_comm_graph except that type is one of G00, G01, G10, G11, G20, or G21.
• Execution of Treatments
  • sbg_treat -tr=treatment dot_file ord_file - main program for all treatments in the paper other than dot and tr23. More detailed information is available.
• Evaluation of Results
  • sbg_cn_eval dot_file ord_file - outputs the number of crossings for the graph specified in the dot_file given the ordering specified in the ord_file.
  • sbg_fstats - a "quick and dirty" program for getting min, average, max, and standard deviation from a collection of data; input (standard input) is a list of numbers, output (standard output) has 4 tab-separated numbers: minimum, mean, maximum, and standard deviation.
  • sbg_gstats - a program for getting detailed information about a specific input graph, such as number of nodes on each layer, number of edges, minimum, maximum, and average degree, etc.