The Pancake Stack Machine
ECE 5760 Cornell University

Introduction
Nakano, K., et.al.(refs below) describe two versions of a small stack machine suitable for implementation on an FPGA and they give the Verilog source code on their web site. The design was ported to the DE2 board and extended to have a richer set of opcodes and i/o ports. I wrote a simple assembler and compiler for the architecture and implemented serial communication routines. The compiler supports inline macros, functions, one dimensional array variables, and the usual if-then-else-endif and while-do-endwhile structured programming. Supplied functions allow you to send and receive integers to the serial interface and to send strings and integers to the LCD.

The newest cpu and example hardware, example software, quartus archive, and compiler can be used to implement the multiprocessor shared-memory VGA graphics example below.

CPU
The cpu is a stack machine. The registers are arranged in a stack with the usual range of arithmetic operators and stack manipulation instructions. There are no named registers except top-of-stack (named top) and next-to-top-of-stack (named next). The CPU design is from http://www.cs.hiroshima-u.ac.jp/~nakano/wiki/ and is GPL licensed. I added load/store opcodes and program counter push/pop. Load and store enable register indirect addressing, while PC manipulations enable functions. The single cycle version with a stack size of 16 occupies about 1100 logic elements (out of 33,000 on the DE2). Reducing the stack size to 8 drops the size to 940 logic elements. Setting QuartusII to optimize for speed (See Tools...Advisors...Timing optimization advisor) increases size to 1000 logic elements and increases the operating frequency to 74 MHz.

The cpu was extended to allow for up to eight in/out ports, with four appearing outside the cpu module. I/O addressing is shown in the opcode table below. The remaining four will be used for internal i/o, perhaps with a timer peripheral. The architecture taken from Nakano, K., et.al is shown below, but modified for 8 i/o ports and with an extra connection from the PC to the data bus (dbus).

CPU opcodes and instruction format

The cpu instruction set is shown below. Notation:

• I is a 12-bit signed integer
• A is an unsigned 12-bit integer
• n is a 3 bit integer (used only as an i/o address)
• top is top-of-stack
• next is second-to-top-of-stack
• PC is the program counter
• mem[A] is the contents of memory location A.
• For binary operations (e.g. add) the stack is always popped so that only the result is on the stack.
  This includes all of the relational operators (e.g. eq, ne).
  

See this page for older versions and develpment sequence.

Simple Compiler (Syrup)

A simple compiler, named Syrup, was written in matlab (also runs in Octave) to make programming easier. A source code is assembled into a mif file, which can be read by the ram block. The link between the mif file and the Pancake cpu ram block is implemented with a synthesis directive in the same statement as the memory declaration and before the semicolon which terminates the declaration.
reg [DWIDTH-1:0] mem [WORDS-1:0] /* synthesis ram_init_file = " test_stack_machine.mif" */ ;
Search for /* synthesis ram_init_file in the verilog file containing the cpu and modify the mif name.

If you change the mif file by recompiling (but keep the mif file name the same), then you can change the memory contents without having to rebuild the whole project:
(1) Click Update Memory Initialization File on the Processing menu.
(2) After using this option, run the QuartusII Assembler (Processing menu...Start...Start Assembler) to generate new programming files for the device.

The compiler_v1_15 syntax is stack based and written in Matlab (version 1.0, compiler_v1_12). A description follows:

• A program consists of up to 5 kinds of sections:
  • Constant declarations denoted by the constant keyword.
    There can be multiple constant blocks per program
    Constants are interpreted as 18-bit 2's complement (roughly +/-131,000).
    All constants are in integer decimal format.
    Constants shorter than 12-bits generate more compact code. Example:
    constant
key3mask 8 ; name -- value pair
redLEDs 3 ; port 3
    
  • Variable declarations denoted by the variable keyword.
    There can be multiple variable blocks per program. Example:
    variable
test ; define a 1 word variable
particle 100 ; define array of length 100
  • Inline function definitions denoted by the inline keyword.
    Each separate inline function starts/ends with inline/endinline.
    Inline functions must be defined before they are used.
    Inline functions may not contain inline functions.
    See the longer example below. Example:
    inline
inc 1 add
endinline
  • Function declarations denoted by the function keyword.
    All called functions must be declared.
    See the longer example below. Example:
    function
getchar
putchar
delay_10
puthex
  • The program denoted by the program keyword. Example:
    

    program ; this section contains the actual program    
    main:  
    0 =count  
    ; loop forever waiting for human input  
    while forever ; never exit  
    do  	
       "enter> putstr gethex crlf  	
       puthex space count puthex crlf  	
       count 1 add =count  
    endwhile ; end of infinite loop

• The program execution starts at the label main: .
  A program section consists of a list of names, operators and structuring statments.
  Space and end-of-line are delimiters and are otherwise completely ignored.
  A semicolon denotes the beginning of a comment, which extends to the end of the current line.
  
• Literal numbers in the code are interperted as 18-bit 2's complement (roughly +/-131,000) and pushed on the stack.
  All numbers are in integer decimal format.
• Using the name of a constant or variable in the code places it's value on the data stack.
  For example, using the definitions above redLEDs key3mask add =test puts the value 11 into the variable test.
  Using a form such as var1[var2] treats var2 as an index into var1 and places the value of the indexed variable on the stack.
  Using =var or =var1[var2] stores the value on the stack to the appropriate location. 
  For example the following code increments the variable count by pushing the memory value onto the stack, pushing 1 onto the stack, adding them, and popping the stack back into memory.
  count 1 add =count
• Available stack operators are:
add, sub, mul, mfix, shl, shr, asr, band, bor, bxor,
and, or, eq, ne, ge, le, gt , lt, neg , bnot , not, drop, over. 
  The operators act  the same way as the respective assembly opcodes.
• "string places the string on the stack (with a character count) to be printed by putstr (see below).
  For example using "enter> places the characters enter> on the stack with the e at next-to-top of stack and the character count at top-of-stack..
  The limit is about 12 characters before you overflow the stack! Always follow a quoted string with putstr.
• Input and output are indicated by in[const] and out[const].
  For example using the constant redLEDs defined above out[redLEDs]
• The entry point of a called function is indicated by funct_entry:
  You invoke the function by using the name funct_entry. The exit point of a called function is indicated by return.
  Called functions must be declared as shown in the longer example linked below.
  
• You invoke an inline function by using its name. For example if the following inline is defined:
  inline make_vga_addr
8 shr 9 shl =temp
8 shr temp add
endinline
  Then later in the program you can use the inline function, in this case by pushing coordinate values on the stack
  and using the inline name
  y[count] x[count] make_vga_addr out[vga_addr]
  
  
• Conditional operators are if then else endif.
  For example the following compares an array variable to 480 and resets it to a lower value if it is too large.
  if x[count] 480 gt
then 478 =x[count]
endif
  
• Repeat operators are while do endwhile.
  For example the following compares counter2 to zero and increments the counter until it overflows.
  while counter2 0 ne
do counter2 1 add =counter2
endwhile
• The assembler is embedded within the compiler. The syntax is opcode.operand or opcode. if there is no operand.
  The period is required for assembler commands. The compiler merely inserts the assembler command into the code.
• Error messages will indicate a unrecognized token (e.g. whilex instead of while), and various assemble errors, like unrecognized symbol, bad opcode, etc.
• There are eight locations reserved for unnamed temporary results at memory addresses 4 to 11. An example follows which swaps the top-of-stack and next-on-stack.
  inline swap
pop.4 ; locs 4&5 are hidden temp locations
pop.5
push.4
push.5
endinline
  

The compiler generates code to initialize the return stack and then jumps to main.
Code starts executing at memory location zero, but your program starts at main:.
The return stack is allocated in high memory, with variables just below. There is no collision detection between code and variables.
Note that the parser is really stupid! No are spaces allowed between equal sign and variable name. No spaces allowed in indexed variable syntax.

Compiler wish list: Local variables, nested inlines, "include", variable/array initialization

Compiler Example

A short example shows how to blink LEDs. It shows the five basic sections of a program:

1. constant section. This section assigns symbolic names to numerical constants.
2. variable section. This section defines memory locations to hold 18-bit variables. If a number follows the variable name, then the number defines the size of the array.
3. inline function definitions. This section allows you to associate arbitrary code with a name. There is no call-return overhead because the code is simply inserted in line.
4. function entry definitions. This section is necessary because the label handler in the compiler is really stupid. All called functions (not inline) need to be listed here.
5. program section. This section has the actual code, which in this program below just blinks some LEDs and responds to a button press. The if-then-else construct contains three assembler commands embedded in the compiler code.

; This program demos compiler
; with LED output and button input
; ==================================

constant ; named constants
	key3mask 8
	key2mask 4
	keys 1  ; port 1
	keymask 15 ; 0x0f
	pattern2 255 ; 0xff
	pattern3 15 ; 0x0f
	redLEDs 3 ; port 3
	greenLEDs 2 ; port 2
	forever 1 ; endless loop

; ==================================

variable
	test   ; location to push test data
	counter1   ; outer loop counter
	counter2   ; inner loop counter
 
; ==================================
 
inline inc
	1 add
endinline

; ================================

function
	evalkey
	
; =================================
program ; this section contains the actual program

main:
0 out[greenLEDs]; reset the green LEDs
0 =counter1 ; init counter

while forever ; never exit
do
	counter1 inc ; get the counter and increment
	dup ; copy stack top 
	out[redLEDs] ;output one copy, one on stack to store
	=counter1  ; save the counter

	;slow it down with an inner loop counter
	1 =counter2 ; reset and store inner counter
	while counter2 0 ne ; compare stack top to zero
		do counter2 inc =counter2 ; inc the counter
	endwhile	;end of inner loop	

	; detect some button presses
	if ; is KEY[3] pressed?
		key3mask evalkey ; detect 4th bit set
	then ; key 3 is pressed
		pushi.pattern2 out.greenLEDs   
	else ; key 3 is not pressed
		pushpc.  out[greenLEDs]
	endif	
endwhile ; end of outer loop

;=== read keys function ====
; enter with a switch selector bit on the stack
; exits with a TRUE/FALSE for match/nomatch on stack
evalkey: 
	in[keys] bnot ; invert so key-down==1
	keymask band ; use only lower 4 bits
	eq ; compare to specific_keymask
	return

;===end of code ============================

Multiprocessor graphics

Three fast processors were hooked up to SRAM to control the VGA. A hardware SRAM memory multiplexer was built to give priority to reset, then to the VGA controller, then each of the three cpus. The source code has to signal that it wants SRAM access, then wait for SRAM available, then read/write and then signal completion. SRAM access is interleaved between the VGA controller and the three cpus. The VGA controller gets access on every VGA clock high, while the cpus share every VGA clock low. This works becuase memory is being clocked twice as fast as the VGA clock. On every VGA clock high, an address is set up based on the VGA address generator. On the VGA clock low, the SRAM data for the VGA is buffered into a register, while the address for the cpu read/write is set up. On the next VGA clock high, the SRAM data is buffered into a register for each cpu, while the next VGA controller read is set up. Execution time for the code speeds up by a factor of five for 1200 particles on each cpu producing an aggregate of around 32,000 particles

A ROM character generator for VGA was built, based on the data from ECE 320 at BYU. The file from BYU is here, and the matlab program to convert it to an Altera mif file is here, and the mif file is here. The ascii character code is multiplied by 16 to from the base index for a character. The data at the base index location is the top byte (of 16) of the character image. The high order bit of the byte is the left-most pixel of the top line of the character. The ROM was connected to i/o ports on the stack processor, cpu 1, where a small routine reads the ROM and outputs colors to the VGA SRAM interface.

Multiprocessor data sharing

The SRAM interface to the VGA display actually has over 100,000 unused bytes which are not displayed, but the unused memory is in small chunks. The biggest piece of available memory is from address 246,400 to 262,144, or about 16 kbytes. These unused locations can be used to share non-graphics data between processors. We need 16-bit read/write functions and a mutex to lock memory. The SRAM switch used in the graphics functions above was extended with new functions to allow 16-bits to be written (the graphics interface writes only single bytes). The mutex is implemented using hardware test-and-set, clear, and read instructions. The hardware switch prioritizes memory access first, then mutex operations. On the processor side, the program must: (1) set up an sram read, write, or mutex operation, (2) assert a request, (3) wait for access achnowledgment, (4) do the read/write (5) de-assert request. The test program computes a diffusion-limited aggregation, as above, maintains a shared (mutex protected) count in sram, and maintains a shared run/done flag in sram. (hardware, software, archived project). And a video of the aggregate growth. The image below shows two counters in the upper left. The green counter is from shared, mutex protected memory. The red counter from shared, unprotected memory. The unprotected count is almost always lower than the protected count because of rare (but inevitable) overlap of two cpus trying to update the count at the same time. Another set of mutexes guarantees that cpu 2 and 3 will finish before cpu 1 tries to print the final count. It does this by setting a lock for cpu 2/3, then having each cpu clear its lock when it finishes.

The processor interface to the memory switch uses several i/o ports:

• out0 for sram address or mutex number
• out1 for data to write to sram
• out2 for control (see below)
• in1 for data from sram or mutex
• in2 for access acknowledge from the switch.

The control word on out2 has the following format. The 4 request lines are mutually exclusive.

• bit 0 low =>write enable for sram
• bit 1 => if 0 => write low byte; if 1 => write high byte
• bit 2 high => request sram access
• bit 3 high => full word read/write (low for VGA byte read/write)
• bit 4 high => request mutex test and set
• bit 5 high => request mutex read
• bit 6 high => request mutex clear
  

The seven functions to access shared memory/mutex are written as inline functions described in the table below. The test-and-set operation on a mutex is atomic. It is guaranteed that if two cpus both try to set a mutex at the same time, only one will succeed, and they both will agree which one has set it.

References:

Nakano, K.; Ito, Y., Processor, Assembler, and Compiler Design Education Using an FPGA, Parallel and Distributed Systems, 2008. ICPADS '08. 14th IEEE International Conference on; 8-10 Dec. 2008 pages: 723 - 728 (Nakano, K.; Ito, Y.; Dept. of Inf. Eng., Hiroshima Univ., Higashi-Hiroshima, Japan)

Nakano, K.; Kawakami, K.; Shigemoto, K.; Kamada, Y.; Ito, Y. A Tiny Processing System for Education and Small Embedded Systems on the FPGAs, Embedded and Ubiquitous Computing, 2008. EUC '08. IEEE/IFIP International Conference, Dec. 2008 pages: 472 - 479

John S. Loomis, Digital Labs using the Altera DE2 Board, http://www.johnloomis.org/digitallab/, Electrical and Computer Engineering, University of Dayton, Dayton, OH 45469-0232

Copyright Cornell University March 20, 2013 Bruce Land