1. reads MEMSIZE numbers from an external memory and writes them to an internal memory (I call these numbers the ‘database’)
2. reads 1 number from another external memory (I call this number the ‘query’)
3. determine if the query is equal to any of the database numbers.

Attempt #1

Mitrion-C 1.5;

MEMSIZE = 100;
MemElem = typedef int:8;

AttRAM = typedef mem MemElem[MEMSIZE];


(bool ,AttRAM ) main(AttRAM RAM0_it0, AttRAM RAM1_it0)
{

    LUT_it0 = _memcreate(mem MemElem[MEMSIZE] LUT_it_last);
    LUT_it_last = LUT_it0;
    AttRAM  LUT_it3 = LUT_it0;


    (MemElem list, LUT_it2) =
    foreach (i in <0 .. MEMSIZE-1>)
    {
	    d = memread(RAM0_it0, i);
	    LUT_it1 = memwrite(LUT_it0,d,i);
    } (d,LUT_it1);
    
    MemElem query = memread(RAM1_it0, 0);
    
    bool e = false;
    (found,LUT_it4)= for (i in <0 .. MEMSIZE-1>) {
    //found = for (element in list) {
	(element,LUT_it3) = memread(LUT_it2, i);
	e = if ( element == query) true else e;
    } (e,LUT_it3) ;

} (found, LUT_it4);

Observations:
Too sequential!!

Results:

Attempt #2

Mitrion-C 1.5;

/*
Given a list of size LISTSIZE determine if it contains duplicates.
Version 2.
*/

LISTSIZE = 10;
ElemType = typedef int:8;


(bool) main(ElemType  list)
{
    vector = reformat(list, [LISTSIZE]);
    comp_list_of_lists = foreach (e,i in list  ,<0 .. LISTSIZE-1>) {
        comp_list = foreach(f,j in vector,[0 .. LISTSIZE-1]) {
            comp = ( (i!=j) && (f == e));
        } comp;
    } comp_list;
    
    gathered_comp_list = foreach (e  in comp_list_of_lists) {
        temp_vector = reformat(e, [LISTSIZE]);
        bits:LISTSIZE scalar = temp_vector;
        f = if ((uint:LISTSIZE)scalar != 0) true else false;
    } f;
    
    regathered_comp_list = reformat(gathered_comp_list, [LISTSIZE]);
    bits:LISTSIZE scalar = regathered_comp_list;
    bool found = if ((uint:LISTSIZE)scalar  != 0) true else false;
    watch found;
} found;

Observations:
Creates MEMSIZE structures in parallel. For example, here’s the resulting structure for MEMSIZE=10.

Results:

Attempt #3

Mitrion-C 1.5;

MEMSIZE = 10;
SEARCHSIZE = 10;
MemElem = typedef int:8;
bits:SEARCHSIZE ZERO = 0x000;

AttRAM = typedef mem MemElem[MEMSIZE];

(bool) main(AttRAM RAM0_it0, AttRAM RAM1_it0)
{
    // This is the internal memory
    LUT_it0 = _memcreate(mem MemElem[MEMSIZE] LUT_it_last);
    LUT_it_last = LUT_it0;
    AttRAM  LUT_it3 = LUT_it0;

    // Read from external memory and write to internal LUT
	
    (MemElem list, LUT_it2) =
    foreach (i in <0 .. MEMSIZE-1>)
    {
	    d = memread(RAM0_it0, i);
	    LUT_it1 = memwrite(LUT_it0,d,i);
    } (d,LUT_it1);
	
    // Read the query
    MemElem query = memread(RAM1_it0, 0);

    // Compare query against each element in the DBase
    (found_list,LUT_it04)  = foreach (i in <0 .. SEARCHSIZE-1>) {
		(element, LUT_it3) = memread(LUT_it2, i);
		e = if ( element == query) 1 else 0;
    }(e, LUT_it3);

    bool e = false;
    found_vector = reformat(found_list, [SEARCHSIZE]);
    watch found_vector;
    bits:SEARCHSIZE scalar = found_vector;

    bool found = if ((uint:SEARCHSIZE)scalar > 0) true else false;
    // recred(found_vector);
    watch found;

} (found);

Observations:
????

Results:

Attempt #4

Mitrion-C 1.5;

MEMSIZE = 100;
SEARCHSIZE = 100;
MemElem = typedef int:8;
bits:SEARCHSIZE ZERO = 0x000;

AttRAM = typedef mem MemElem[MEMSIZE];


(bool) main(AttRAM RAM0_it0, AttRAM RAM1_it0)
{
    // This is the internal memory
    LUT_it0 = _memcreate(mem MemElem[MEMSIZE] LUT_it_last);
    LUT_it_last = LUT_it0;
    AttRAM  LUT_it3 = LUT_it0;

    // Read from external memory and write to internal LUT
    (MemElem list, LUT_it2) =
    foreach (i in <0 .. MEMSIZE-1>)
    {
	    d = memread(RAM0_it0, i);
	    LUT_it1 = memwrite(LUT_it0,d,i);
    } (d,LUT_it1);
    
    // Read the query
    MemElem query = memread(RAM1_it0, 0);
    
    int:8 i = 0;
    bool e = false;
    // Compare query against each element in the DBase
    (found,LUT_it04)  = while ( (e == false) && ( i < SEARCHSIZE) ) {
    //found = for (element in list) {
	(element, LUT_it3) = memread(LUT_it2, i);
	e = if ( element == query) true else false;
	i = i + 1;
    }(e, LUT_it3);
    


} (found);

Observations:
The use of while serializes everything. Avoid!

Results:

What are the FPGA models included in the HC-1.

Response:

The HC-1 is organized as follows:

Each of the 4 FPGAs is a Virtex 5 LX330. For more information, see:
Virtex-5 FPGA Family Overview : http://www.xilinx.com/support/documentation/data_sheets/ds100.pdf
Virtex-5 FPGA User Guide: http://www.xilinx.com/support/documentation/user_guides/ug190.pdf

Each of the 8 memory controllers supports two memory channels populated with scatter-gather DIMMs. The coprocessor in our system has a total memory of 16GB.

Here is some basic information from the Virtex 5 LX330 data sheet:

With respect to MitrionC the most important (limiting) resource are the Flip/Flop.  Each Virtex-5 FPGA slice contains four LUTs and four flip-flops. Thus the total amount of available F/Fs is 51,840 x 4 = 207,360. Usually an FPGA will have 100% slice utilization at around 50-60% flip-flop usage, thus you can safely count on 103,680 F/Fs (for each FPGA).

Here is an illustration of a Virtex 5 slice.

Each DSP48E slice contains a 25 x 18 multiplier, an adder, and an accumulator.

You may request your account to this machine by emailing: rafael (dot) arce (at) upr (dot) edu.

Here is a log of what happens if I run mitrion with the -sizes option. Can you tell me what is wrong?

% mitrion -batch -sizes dumb_search_v02.mitc
Mitrion SDK PE v1.5.3 build 537 - http://www.mitrionics.com
2008/11/11 14:56:05 GMT

Your code will now be transfered to secure.mitrion.com
over a secure connection and there it will calculate
the resource usage of the Virtual Mitrion Processor.

Are you sure you want to continue? [yes/no] yes

Please select a hardware platform for size estimation.
1) SGI RC100 Virtex 4 LX200
2) Cray XD1 with Virtex 4 LX160
3) Cray XD1 with Virtex 2 VP50
4) Nallatech H101 Virtex 4 LX100

Enter a number: 4
------------[ Connecting to server

*** ERROR: Error connecting to Mitrion server
------------[ Doing shutdown due to errors.

Response from Mitrionics support:

Unfortunately, the sizes server is currently down (it will likely be down for some months). However, you can use the sizes option in the configurator-enabled version of the SDK without the sizes server (i.e. the one for the Convey machine). Also, if you have a Linux or Windows machine, you can install the SDK v2.0 there: That can give you size information directly in the GUI for every node and function.

Follow-up question:

Where in the gui is it that I can see the sizes? What is the mitrion command that I should be using to see the sizes? I am using version v2.1.0.

Response to follow-up question:

You should use the -gui-optimized flag to get size information (though the -gui flag will give you more accurate location information). Then either press shift and hover over a node, or tick the popups checkbox and hover over a node.

Not all nodes cause flip-flops to be consumed, and we only measure and report flip-flop usage. LUT usage after synthesis and P&R is so unpredictable that it is useless as a predictor of FPGA-fit. However, flip-flop usage is useful and usually an FPGA will have 100% slice utilization at around 50-60% flip-flop usage.

Is there any way of converting a type bits:1<10> to a type bits:10?

Response from Mitrionics Support:

Sure, just reformat the list to a vector:

bits:1[10] vector = reformat(list,[10]);

then do a direct assignment bits:10 scalar:

bits:10 scalar = vector;

The bits type will accept literally anything (including a collection,
such as a vector) as long as the width of the bits type and the source
type coincide. From the bits type you can then further convert into the
other data types.

I am trying to code a program that reads 10 numbers from an external
memory and 1 query number from another external memory. The 10 numbers are written to an internal memory. Then I would like to determine if the query is equal to any of the 10 numbers.

Here is my program. I generate a list of booleans that contains the
comparisons of the query against each of the 10 numbers. How do I
specify that I would like a parallel ‘AND’ function performed over the
10 booleans?

Mitrion-C 1.5;

MEMSIZE = 10;
MemElem = typedef int:8;

AttRAM = typedef mem MemElem[MEMSIZE];

(bool) main(AttRAM RAM0_it0, AttRAM RAM1_it0)
{
// This is the internal memory (LUT)
LUT_it0 = _memcreate(mem MemElem[MEMSIZE] LUT_it_last);
LUT_it_last = LUT_it0;
AttRAM  LUT_it3 = LUT_it0;

// Read the 10 numbers from external mem and write them to LUT
(MemElem<MEMSIZE> list, LUT_it2) =
foreach (i in <0 .. MEMSIZE-1>)
{
d = memread(RAM0_it0, i);
LUT_it1 = memwrite(LUT_it0,d,i);
} (d,LUT_it1);

// Read the query
MemElem query = memread(RAM1_it0, 0);

// Compare query against numbers
found_list  = foreach (i in <0 .. MEMSIZE-1>) {
element = memread(LUT_it2, i);
e = if ( element == query) true else false;
} e ;

bool e = false;
found_vector = reformat(found_list, [MEMSIZE]);
watch found_vector;

found = myAND(found_vector);
watch found;

} (found);

// There must be a cleaner way of doing this!!!!!

bool myAND(bool [MEMSIZE] x) {
res = x[0] || x[1] || x[2] || x[3] || x[4] || x[5] || x[6] || x[7]
|| x[8] || x[9];
}res;

Response from Mitrionics support:

There are a couple of alternative solutions to your problem. For one,
since you are only comparing a single element at a time (you are taking
the elements you are comparing from a memory), you could do the test
sequentially (i.e. the same way as you did the max() function in the
training, but now an and() or or() function instead).

Alternatively, you could use a recursive tree reduction on your
collection; I included a general-purpose tree-reducer below. Keep in
mind though, tree-reducers are a usually wasteful of LUTs unless you can
feed them with wide data (i.e. vectors as input). In this particular
case, you are only doing a bitwise boolean, so it will likely be cheaper
than a loop, but that is not generally the case.

You should change the internal reduce()-function to do a logical
or-comparison to fit your program.

I should also comment on a construction in your code in lines 12-13 and 21:

LUT_it0 = _memcreate(mem MemElem[MEMSIZE] LUT_it_last);
LUT_it_last = LUT_it0;
…
LUT_it1 = memwrite(LUT_it0,d,i);

It is dangerous to get into the habit of doing like this. If you
sometime in the future call this function from within a loop, it will
cause a race-condition. The effect of this is similar to freeing memory,
and then using the pointer to the freed memory.

Instead, you should accept the instance token from line 30:

(element, LUT_it3) = memread(LUT_it2, i);

return it from the loop, and then put that into LUT_it_last instead of
LUT_it0:

LUT_it_last = LUT_it4;

// A general purpose reduction tree function. Change the operation
// of the internal reduce() function to the operation required.

recred(a)
{
   reduce(a, b) a + b;

   half = length(typeof(a)) / 2;
   res = if(half > 0)
   {
       lower = foreach(e in a < !-- half) e;
       upper = foreach(e in a /< half) e;
       res = reduce(recred(lower), recred(upper));
   } res
   else
   {
       vect = reformat(a, [1]);
       res =  vect[0];
   } res;
} res;