Router Utilities

May 11, 2006

Overview

The ROUTER utility accepts netlist descriptions of architectures and generates routing tables. Routing tables list the pathways from each device to every other device in an architecture. The ROUTER and routing tables are intended for use with the Performance Model Library models. However, the ROUTER could be used for other applications as well which need routing information.

During simulations, processor models reference the routing tables to send messages through the simulated networks. Building a routing table prior to simulation is more efficient than searching for pathways at runtime, because it finds all the paths once, instead of repetitively.

This ROUTER is based on a breadth-first version of the Dijkstra shortest distance search algorithm. It is efficient, rapid, and general-pupose.

Several heuristical improvements have been incorporated to balance usage of network resources. The ROUTER keeps track of how many paths have used each link. When two otherwise-equivalent pathways are found between PE's, the ROUTER chooses the least used path. This avoids the pathological case of mapping all routes to only one of multiple equidistant paths.

After determining the routing table, the ROUTER produces a usage summary of statistics on how well the paths were balanced. It shows what links, if any, were not used in any path; what links were used by the most paths (potential hot-spots); and the average, peak, and minimum the number of paths using a given link.

For many uses and architectures, the paths found by the automatic router are sufficient without further optimization. However for special cases, the resulting routing table can be manually edited. It is produced in an easy-to-read ASCII format. The ROUTER utility is a convenient starting-point for building optimal routing tables.

Usage

The ROUTER builds the routing-table by reading the netinfo file produced by the CSIM simulator when first brought up with an new architecture. The following proceedure should be used:

Define your architecture in CSIM models and compile the simulation to produce the sim.exe .
Example:
- gui arch.sim
  (Enter you topology.)
- csim arch.sim
  (From GUI: Tools / Build Simulation.)
Invoke simulation with -net option.
(From GUI, this happens automatically as the second part of Tools / Build Simulation above.)
Example:
- sim.exe -net
This produces the netinfo file.
Run the ROUTER:
(From GUI: Tools / Build Routing Table.)
Example:
- router netinfo
This produces the netinfo.rte file containing the routing table.

Port Naming Convention

Only the ports on multi-port devices need to be entered into the routing path. (Dual-port devices go straight through by default!). By convention, multi-port port-names should end in numbers, such as p7, or io_1, etc.. The ROUTER will extract these numbers and use them in naming each port in the routing path. Ports not ending in numbers will not be entered into the routing path. See the example topology in figure 1 below.

Figure 1 - Example architecture topology.

Device Name-to-Number Binding

The netinfo file establishes a name-to-logical-ID-number for each device in your modeled system. You are free to edit the name-to-ID-number bindings in the netinfo file prior to routing and software generation.

Routing Table File

The basic routing-table is a three-dimensional array. The pathway from any source device to any destination device is recorded, -and can be retrieved-, by placing the source device in the first index of the array and the destination device in the second index. The third index is used to retrieve the port assignment for each hop along the path.

	ROUTE_TABLE[ source, destination, hop ]

The pathway from each source device to each destination device is listed in the routing table as follows:

	alt  src_dev - dst_dev : x1 x2 x3 x4 x5

This line specifies that the sequence of ports to pass-through to send a message from src_dev to dst_dev is {x1 x2 x3 x4 x5}, where x1 x2 x3 x4 x5 are the respective port numbers on the intermediate network elements. The first item on the line, alt, is the alternate path number. The primary path from a given source to a given destination is alternate path 0. If there are multiple pathways between a given source and destination, the alternate paths can be listed with lines having distinct alternate path numbers. Alternate pathways are described further below.

The entry can be interpreted as,

	To send a message from src_dev to dst_dev, go through port
	x1, then port x2, ... and finally through port x5.

Advanced Router Aspects

The description above covers the basic ROUTER functions. Additional router features include:

Multiple alternative paths - Finds multiple paths between each source-destination.
Variable routing cost - Considers a non-unity routing-cost for each link.

Multiple Path Routing

The ROUTER finds multiple alternate paths, if they exist, between each source and destination. By default, it will attempt to find as many as two paths for every source-destination pair. You can find more alternate paths by using the -alt command-line option. For example:

	router  -alt 5  netinfo

finds as many as five (5) alternate paths, if they exist.

The ROUTER generates a routing table containing four (4) indices, which can be thought of conceptually as the following multi-dimensional array:

	ROUTE_TABLE[ alternate, source, destination, hop ]

The corresponding entry in the routing table for the hops in the given path, from a source, and to a destination is listed in the routing table as:

	alternate  src_dev - dst_dev : x1 x2 x3 x4 x5

The ROUTER orders the paths found according to their distance goodness or in other words, routing-cost. For example, if the ROUTER is instructed to find the 5-best paths, and for a given source-destination pair it finds:

Two paths having 3-link-hops (Path-cost = 3)
One path having 5-hops (Path-cost = 5)
Eight paths having 9-hops (Path-cost = 9)

It will list the two cost=3 paths as alternates 0 and 1, the cost=5 path as alternate 2, and it will pick two of the cost=9 paths as the remaining alternates 3 and 4.

Variable Cost Routing

The ROUTER utility can consider non-unity routing-costs for each link while selecting pathways. By default, link-costs are normally equal to 1.0, but can be set to any floating-point value. A path distance is computed as the sum of its link costs. The Dijkstra router finds the lowest-cost (shortest-distance) pathways.

The link-costs can be specified with the CSIM GUI. The cost is specifiable individually for each direction on each link. If the cost is identical in both directions, you only need to enter one number. If it is non-symmetrical, specify the two costs with a space between them.

The link costs can be used to control the routing-paths chosen. For example, you may wish to avoid a particular link from being used. Then set its routing-cost to infinity (a large number). Conversely, you may not want an intermediate link to be considered as part of the routing-cost. Then set its cost to zero.

Advanced Topics - Customizing Routing Tables

Sometimes you may need specialized routing tables. For example, suppose you have two types of messages in your network: control and data, and you want the control messages to use different pathways from those of the data messages. One way to do this is to build and use two routing tables: one for control and one for data messages.

There are various ways to create custom routing tables. One way is to edit the routing-table file directly, since it is editable. However, this is usually very tedious because routing files can be very large. Another way is to write an adhoc program that explicitly writes the routings you wish to use for your architecture. However, we will look at a more automatic method that exploits spoofing the router by editing the netinfo file. This is much more managable than editing the routing-table.

Because the router is a drone that simply finds the shortest way to get from point A to point B in any arbitrary network, there are often convenient and clever ways to trick the router to produce just the routes you want.

For example, in the control/data example above, if you want all control messages to flow over a VME bus, but no application data should flow over the VME bus. Then create two copies of the netinfo file. Call them: netinfo_Control and netinfo_Data. To avoid the data messages from traversing the VME bus, remove the VME bus from the netinfo_Data file and run the ROUTER on it instead of the original netinfo file. Because you have broken the VME path, the router will find alternate pathways through which to route all data-messages.

A convenient way of removing unique keywords is through the grep -v command which returns all lines from a file except those that contain a specified search-string. For example,

	grep -v VME netinfo > netinfo_Data

would build the netinfo_Data file. Such procedures can be put into a Make.com command script for automatically configuring the routing files whenever you change your model architecture.

Likewise, dedicated pathways for the control messages can be forced by cutting any critical links that would otherwise provide shorter paths through links that are to be data-dedicated. Note that not-all the data-dedicated paths need to be cut as long as there is a shorter control-path to get to the same place. The router will simply ignore any paths that are longer.

Reducing Routing-Table Size

Many devices do not ever originate or absorb messages. Therefore, they do not require entries in the routing table. Only the actual source and destination devices really matter, because these will be the source/destination indices of the routing-lookup table used to get messages to-or-from these devices. Such devices are usually the Processor-Elements or Memories in a modeled system. Intermediate devices such as buses and crossbar-swicthes do not need source/destination entries, because they are neither the sources nor the destinations of messages.

Devices that can not be used as a source or destination, may be classified as such, thus reducing the size of the routing file. To classify a device as a non-source, non-destination or as both a non-source and destination, insert one of the following lines in the device behavioral description following the line

	DEFINE_DEVICE_TYPE:     <device_type>
	
	 DEVICE_CLASS=(nosource);
	 DEVICE_CLASS=(nodest);
	 DEVICE_CLASS=(nosrcdst);

Routing Waypoints and Explicit Routes

The CSIM tools allow you to guide the paths that messages are routed in the system when multiple alternate paths exist. This is done by specifying key hardware nodes (waypoints) that the message must pass through. See Routing Waypoints for more information.

Command-Line Options

The ROUTER supports the following command-line options:

[second_file] - The second file on the command-line specifies the name and location of the resulting routing table. By default, the routing table has the same root-name as the input netinfo file, but with the .rte extension, (ex. netinfo.rte), unless overrridden by this option.
-alt - Specifies the number of alternate paths between each source and destination to find distinct routes for. Default = 2.
Example: -alt 5
-n - Specifies the highest routed source or destination device number.
Example: -n 200
-v - Sets the verbosity.
Example: -v 10
-check1 - Causes the Router, -after generating the routing table-, to check every generated route for correctness. This is normally unnecessary, as the Router is a correct-by-construction tool. However, the check is provided as part of the Router's built-in testing capability which helps us validate and maintain the tool. It can be called upon if ever the Router is suspected of making an error, or to be doubly sure of the generated routes.
-check2 - Causes the Router, -after generating the routing table-, to exhaustively check for missing, or better, paths. For independence, this check uses a totally different, but much slower, routing algorithm method than the Router's primary algorithm. This check is not normally needed, but is provided as part of the Router's built-in testing capability which helps us validate and maintain the tool.
-check3 - Enables you, the user, to get detailed information about specific paths from the generated routing table after routing is completed, by interactive query. After the routing table is generated, you will be prompted for a source-destination pair. It will then show you, the intermediate nodes and ports for each of the alternative paths. Importantly, this also shows you the so-called invisible devices (devices without numbered ports do not show up in the routing path) and the corresponding unnumbered ports used, along the path. You can continue to ask for other routes or exit as prompted.
-fullpath - This produces a more explicit routing file with the format being, for example:
```
         Path 233 586 0: <233 4> <231 3> ... <45 2> 
```
The tags in this format are easily parsed by user-scripts. For example, you can search for any route which ran through, say, device <231 and device < 45, and then, perhaps substitute a preferred route-segment for that segment of the route. When invoked, this option prints a message telling you the name of the file it saves the explicit format to, such as netinfo.fullpath.
Note that the fullpath file is approximately four times (4x) larger than the normal (.rte) routing file, due to the extra tag-characters and device numbers for each hop in the paths.
The syntax is:
```
 Path #1 #2 #3: <#4 #5> ...  <#6 #7> 
```
Where:
```
	#1 = Source device number.
	#2 = Destination device number.
	#3 = Alternate path number.
	#4 = First device in path (same as #1).
	#5 = First port number in path.
	... = All the intermediate hops.
	#6 = Last device hop in path (same as #2).
	#7 = Last port number in path. 
```
Note that path-hops through un-numbered ports of devices, which do not apear in the normal .rte files, will appear in the fullpaths file, but with negative port-numbers. The negative value is a place-holder for indicating an otherwise un-numbered port.
If you alter the paths in the netinfo.fullpaths file, you can translate the format back to the normal .rte format with the translate_paths.c program.
-cpc filename - Cross-port routing-cost specification. This option allows consideration of intra-device port-to-port costs to be used from file 'filename' in determininig the best routing paths. Certain port-to-port connections may be inhibited, thus reducing the size of the routing file. For detailed description of its use, see Cross-port routing-cost specification.
-testbox - Generates full routes for the 'netinfo.rte' file with non-numeric ports specified as negative numbers. A second file called 'portnames' is also generated which shows the mapping between the negative port numbers and the device port names. See Displaying Selected Routing Paths for further information on usage.

Router FAQ - Debugging Routes