and tail pointers. The FIFO could also be generic (polymorphic) in its content type, instead of just containing int values.

Many modules have FIFO-like interfaces—that is, flow-controlled ports that accept or yield values. We can define polymorphic interfaces for this:

 

interface FIFOin #(type t); method Action enq (t x);

endinterface

 

interface FIFOout #(type t); method t first (); method Action deq ();

endinterface

Other than in the syntactic details,
these capabilities are similar to what is
seen in object-oriented languages. The
key difference is that while OO meth-
ods are fragments of sequential pro-
cesses, BSV methods are fragments of
rules and have guards.

figure 5. interface type declaration.

 

interface XBar #(type packet_t); interface List #(FIFOin #(packet_t)) input_ports; interface List #(FIFOout #(packet_t)) output_ports;

endinterface

 

figure 6. a crossbar switch module.

module mkXBar #(Integer n,
Function UInt #( 32) destinationOf (t x),
Module #(Merge2x1 #(t)) mkMerge2x1)
(XBar #(t) );

List#(Put#(t)) iports; List#(Get#(t)) oports;

//(P1)

//(P2)

//(P3)

 

if (n == 1) begin FIFO#(t) f <- mkFIFO; iports = cons(toFIFOin(f),Nil); oports = cons(toFIFOout(f),Nil);

end else begin

XBar#(t) upper <- mkXBar(n/2, destinationOf, mkMerge2x1); XBar#(t) lower <- mkXBar(n/2, destinationOf, mkMerge2x1); iports = append ( upper.input_ports, lower.input_ports); let midports = append (upper.output_ports, lower.output_ports);

List#(Merge2x1) merges <- replicateM (n, mkMerge2x1); oports = map (oport_of, merges);

for (Integer j = 0; j < n; j = j + 1)
rule route;
let x = midports [j].first();
let jDest = computeRoute (destinationOf (x), j, n);
if (jDest == j) merges [j] .iport0.enq (x);
else merges [jDest].iport1.enq (x);
midports [j].deq();
endrule
end
interface input_ports = iports;
interface output_ports = oports;

( 2 in, 1 out), and routing logic ( 1 in, 2 out). Figure 5 shows the interface type declaration.

It is generic, or polymorphic, in the type packet _ t of packets flowing through the switch. It is nested, or hierarchical, in that it is defined in terms of two sub-interfaces: input _ ports and output _ ports. These, in turn, use standard List data structures to refer to collections of FIFOin and FIFOout interfaces. Figure 6 shows a module mkXBar implementing this interface.

P1-P3 are parameters: n requests an n × n switch; destinationOf is a function from packets (of type t) to destinations (of type UInt #( 32), unsigned 32b integers) that can be used to take routing decisions; and mkMerge2× 1 is a constructor for the 2-input, 1-out- put merge modules. In the semantics, a module constructor is just a function from parameters to modules. Further, it is a higher-order function—that is, its parameters may themselves be functions and module constructors. These features are standard in advanced programming languages such as Haskell20 and Standard ML (SML) 17 but are very unusual in HDLs, particularly in synthesizable HDLs.

The bulk of the module is a recursive definition of the module. The then part of the big conditional is the base case (n== 1). A 1x1 switch is implemented using mkFIFO. The next line uses functions toFIFOin and toFIFOout (easy; not shown) to separate the FIFO interface into FIFOin and FIFOout interfaces, and builds them into singleton lists iports and oports.

The else part is the recursive case (n> 1). The code first recursively instantiates mkXBar twice, at size n/2, for the upper and lower 2× 2 subswitches. It appends their input _ ports and output _ ports and holds them in the lists iports and midports, respectively. It then instantiates the vertical column of n 2× 1 merge blocks at the right edge of the switch shown in Figure 4 using the library higher-order function replicateM on parameter mkMerge2× 1. It uses the standard library list-process-ing higher-order function map with the oport _ of function (not shown; simply returns the output port of a mkMerge2× 1 module) to create the oports list.