## A Basic Machine Model

**Introduction**: Many machines can be represented using the following simple model. A machine

M = {R,T), consists of:

1. A set of operation types T, such as loads, stores, arithmetic operations, and so on.

2. A vector R = [n, r2,... ] representing hardware resources, where r« is the number of units available of the ith kind of resource. Examples of typical resource types include: memory access units, ALU's, and floating-point functional units.

Each operation has a set of input operands, a set of output operands, and a resource requirement. Associated with each input operand is an input latency indicating when the input value must be available (relative to the start of the operation). Typical input operands have zero latency, meaning that the values are needed immediately, at the clock when the operation is issued. Similarly, associated with each output operand is an output latency, which indicates when the result is available, relative to the start of the operation. Resource usage for each machine operation type t is modeled by a two dimensional resource-reservation table, RTt. The width of the table is the number of kinds of resources in the machine, and its length is the duration over which resources are used by the operation. Entry RTt[i,j] is the number of units of the j t h resource used by an operation of type t, i clocks after it is issued. For notational simplicity, we assume RTt[i,j] = 0 if i refers to a nonexistent entry in the table (i.e., i is greater than the number of clocks it takes to execute the operation). Of course, for any t, i, and j, RTt[i,j] must be less than or equal to R[j], the number of resources of type j that the machine has.

Typical machine operations occupy only one unit of resource at the time an operation is issued. Some operations may use more than one functional unit. For example, a multiply-and-add operation may use a multiplier in the first clock and an adder in the second. Some operations, such as a divide, may need to occupy a resource for several clocks. Fully pipelined operations are those that can be issued every clock, even though their results are not available until some number of clocks later. We need not model the resources of every stage of a pipeline explicitly; one single unit to represent the first stage will do.

Any operation occupying the first stage of a pipeline is guaranteed the right to proceed to subsequent stages in subsequent clocks.