RamInterleave

Illustration of ray casting across a gridThis program addresses grid-based calculation in 1, 2, 3, or more dimensions. It assumes that, at each step of the calculation, a cluster of grid points must be accessed in order to create one output value. It also assumes that grid points are accessed in irregular order, so normal pipelining and temporal reuse techniques can not be applied. This occurs, for example, in ray-casting algorithms and particle-grid calculations, like those illustrated at right.

In this example, each off-grid value along the ray must be computed by interpolating a value from the four nearest grid points. A high-performance application would prefer to fetch all four neighboring grid points concurrently, in one memory cycle, and perform as much of the interpolation as possible in parallel.

Usage

This program generates VHDL code for memory structures that give the desired parallelism, using the on-chip memories in the FPGA. This is a Java program that runs form the Java command line, with the following syntax (assuming that Java is already on the command search path):

java edu.bu.caadlab.MemIntlv.RamInterleave <param> [...]

Command line parameters all have the format <name>=<value>. Parameter names and values are not case sensitive, although output filenames derived from the name parameter may be case sensitive depending on the conventions of the file system. The following table lists the command line parameters available:

Parameter Value Meaning Example
axis sym Name of one of the indexing axes (diumensions). Axes are taken to be in the order specified by the order of the axis parameters. The number of axes is implicitly the number of axis parameters. If no axis parameters are specified, there is assumed to be one indexing axis named X. axis=horizontal
databits sym An integer value, 1 or more, specifying the number of data bits per word of memory. If not specified, a default value of 8 bits is assumed. If specified more than once, only the rightmost instance of the databits parameter has meaning. databits=24
name sym Name to use for the memory component. It not speified, the default "interleaved" is used. If specified more than once, only the rightmost has meaning. name=BiLinearMem
output sym,int[,...]

Specifies one of the parallel output words for the interleaved memory. There must be a separate output parameter for each word generated by the memory. Each output is specified by a name and by its index coordinates, relative to the base index provided as input. The number of indices on each output parameter must match the number of axis parameters (1 by default). There must be one or more output parameters.
Current restrictions: For each indexing axis, at least one of the output parameters must have a zero offset. Negative offsets are not supported.

output=upperRight,1,1
testsize int[,...] Specifies the size of each indexing axis instantiated in the testbench for this memory. There must be a positive value for each of the indexing axes. If not specified, the default is 128 words in each indexing direction. testsize=100,50

Integer values are assumed to be decimal. Symbols (sym in the table above) must be unique, must start with a letter A-Z or a-z, and must continue only with letters or digits 0-9. In particular, underscores may not be used, since they are reserved for symbol generated automatically by RamInterleave.

Sample application

The following section describes the output files generated by the RamInterleave tool. For illustrative purposes, the following command line is used to generate the interleaved memory (watch for command line wraparound caused by the browser):

java RamInterleave dataBits=12 output=north,0,1 output=mid,0,0 output=east,1,0 output=ee,2,0 axis=longitude axis=latitude name=testRam testsize=64,128

     
north    
mid east ee
In this example, the cluster of neighboring grid points fetched at each cycle has the layout shown at right. Only the shaded cells are output. The index pair provided as input to the memory refers to the position of the mid cell (index offset 0,0), and other cells are offset from that position. During a write operation, the indices point to the mid cell and only that word is written.

Output

Output consists of three VHDL files, with names derived from the name parameter:

In the sample application, the namevalue is testRam. Portions of the definition package are shown below.

  subtype testRam_data is std_logic_vector(11 downto 0);

  type testRam_rdIndex is (    -- Index for output vector
      north, mid, east, ee);
  type testRam_output is array(testRam_rdIndex) of testRam_data;

Note that, because all of these symbols are based on the name given at the command line, it is possible for one application to use multiple interleaved memories without interference between the auxiliary symbols the use.

The first line, testRam_data, declares a data word to be output by the test RAM. The current version of RamInterleave does not allow this width to be parameterized, because of VHDL's requirements for the array declared later. The second declaration, testRam_rdIndex, is an enumeration that represents the set of memory words to be fetched as a unit. These values are to be used as indices in the array testRam_rdIndex, decalred next. This array represents the output generated at each memory cycle.

  component testRam is
  generic (
    simulation: boolean := false; -- True in simulation, false for synthesis.
    longitude_length: natural := 128;
    latitude_length: natural := 128);
  port (
    longitude: in natural range 0 to longitude_length-1; 
    latitude: in natural range 0 to latitude_length-1; 
    datOut: out testRam_output;
    wrData: in testRam_data;
    wrEnable : in boolean;
    sysClk : in std_logic );
  end component testRam; 

Every cycle (rising edge of sycClk) is a read cycle. The index values (longitude and latitude) present immediately before the clock edge are used for addressing. The desired set of memory words appears at the datOut output some time later. Setup, hold, and latency times depend on the how the component is synthesized. No check is made that the index values are in range, or the access cluster avoids wraparound at the edge of the memory grid.

If wrEnable is true at the time sysClk goes high, then the value at the wrData input is written. If latitude and longitude indices are held constant across the next rising edge of sysClk, then the data written will appear at datOut(mid) in the next cycle.

The simulation generic should be set false for actual sythesis. Some intermediate addressing calculations may take on invalid values during testing, and this is known to halt some simulators. Since the invalid values never generate incorrect output within the memory's specified operating regime, they are harmless. Setting this generic true generates excess allocation of some data paths internal to the component, to prevent the simulator from halting. A false value generates smaller and potentially faster hardware.

The longitude_length and latitude_length generic values specify the dimension of the memory in each axis. These may be any positive value, up to the amount of RAM available on the FPGA. These allow different instances of the memory to have different dimensions, even within one system. These values are not constrained to be powers of two. There may, however, be a slight advantage in performance and gate count if powers of two are used.


© Tom VanCourt 2006

RamInterleave is distributed in the hope that it will be useful,  but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with RamInterleave; if not, write to the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA

http://www.bu.edu/caadlab