Introduction
============

An implementation of the constraint programming approach to superblock
instruction scheduling for realistic multiple-issue processors described in:

    A. M. Malik, M. Chase, T. Russell, and P. van Beek.  An application
    of constraint programming to superblock instruction scheduling. CP-2008.

The paper reports on experiments on 154,651 superblocks. We have included
here 10,000 benchmark instances. These are some of the harder problems
that we found.


Getting going
=============
% cd Src
% make
% ./schedule.exe ../Architectures/1-issue.xpr ammp/1021.txt


Directory contents
==================

./README.txt		-- This file.
./Instances		-- Directory containing benchmark instances
./Src			-- Directory containing source code
./Architectures		-- Directory containing architecture descriptions


More details on the instances
=============================

The superblocks are from the SPEC 2000 integer and floating point benchmarks.
- superblocks are from before and after register allocation
- the taken=x% values constructed by using profiling using the SPEC
  testing data.
- these instructions have "taken=x%" associated with them:
  BCF, BCT, BF, BT, BFBIT, BTBIT, BCTF, BCTT.
  The x% is the percentage of the time the early exit is taken,
  given that the flow of control has reached this instruction;
  otherwise the flow of control falls through to the instruction
  following the branch.
- the pair of numbers following the taken=x% (a, b) mean the following:
  a = number of times branch is taken
  b = number of times fall through
- other branches are absolute branches such as: CALL, BA, B
- size range: 3 -- 2749
- meaning of edges (i, j) in DAG
  A -- anti dependence: i uses some variables value and j sets that variable.
  M -- memory dependence
  O -- output dependence: both i and j set the value of some variable.
  T -- true or flow dependence: i sets a value that j uses.