1 Introduction2 Background2.1 MIPS Assembly2.2 SHIPs3 Implementation3.1 Instruction Framework3.2 Registers3.3 Arithmetic Operations3.4 Logical Operations3.5 Shift Operations3.6 Branches and Sets3.7 Jumps3.8 Memory Access Operations3.9 Data Movement3.10 System Calls3.11 Cleanup4 Results5 Discussion5.1 Bugs and Limitations5.2 Modifications to the FLEET Interpreter5.2.1 Register Jumps5.2.2 Byte-Addressed Memory Access5.2.3 I/O5.2.4 Suggested Modifications5.3 Future Work6 ConclusionA Fibonacci ProgramA.1 MIPS CodeA.2 FLEET CodeMIPS on FLEETAmir KamilComputer Science Division, University of California, [email protected] 18, 20061 IntroductionThe introduction of multi-core processors by the major microprocessor developers marks a dramatic shiftin software development: parallelism for laptops and desktop machines will no longer be hidden withina micro-architecture, but will be exposed to higher level software. Programmer control of concurrencyand data movement will be necessary in order to achieve maximum performance. Unfortunately, mostmodern architectures and programming techniques were originally designed for sequential programming,and it is not clear that they are ideal in a parallel setting. The FLEET computer [1] is a new architecturedesigned from the ground up with parallelism in mind, providing the programmer with direct control overdata movement and concurrency.Since FLEET is a completely new architecture, programming for it can be quite challenging. Themachine is inherently parallel, so sequential programming techniques do not directly translate to it. Inorder to alleviate this problem, we have developed a translator between MIPS binary code and FLEETassembly. Using this translator, programs written in MIPS assembly can run on FLEET. The eventualgoal is to allow code written in higher-level languages to also run on FLEET by first compiling to MIPSassembly. In this paper, we present the techniques used by the translator to convert MIPS code to FLEETcode.2 Background2.1 MIPS AssemblyWe chose MIPS R3000 assembly as the source of the translator for many reasons. MIPS is a RISCarchitecture, so the instructions it provides are simple and highly regular. In addition, it is widely used inembedded systems, so it has a large code base and many tools, such as the SPIM emulator [3].The translator currently supports the 32 numbered MIPS registers, as well as the $hi and $lo reg-isters used by multiplication and division. It implements integer arithmetic and logic, branches, jumps,sets, loads, stores, data movement between $hi and $lo and the numbered registers, and basic system1calls. The translator does not simulate the MIPS instruction pipeline, and does not insert any delay slotsinto the source code.2.2 SHIPsThe FLEET architecture consists of many small processing elements, called SHIPs. Each element canhave input and output ports, which are connected by a switch fabric to every other port in the machine.Computation is performed exclusively through data movement between these ports. As such, FLEET canbe considered a one-instruction machine, since the only instructions it provides are variants of a singledata movement command, as specified in AM10 and AM11 [4, 6].We used the SHIPs defined in IES31 [5] as the basis of the translator, with some differences. TheFetch SHIP was modified from IES31 to allow a codebag to be released or revoked. The input and outputports were replaced with the boxes of AM10 and AM11. In addition, we found it useful to define newSHIPs in order to simplify the task of the translator.3 ImplementationIn this section, we discuss the details of how MIPS assembly code is translated into FLEET assembly.3.1 Instruction FrameworkThe translator implements each MIPS instruction as a separate codebag. This ensures that instructions canbe properly sequenced so that they do not interfere with each other. Each instruction codebag dispatchesthe next one to the Fetch SHIP, and only releases it when all side effects of the instruction have completed.3.2 RegistersWe implemented MIPS registers on top of the FIFO storage SHIP defined in IES31. The translator onlyuses a single element of each FIFO to represent a register.Registers can never be empty, so they must be initialized by inserting a zero into their respective FIFOunits. A register read simply copies the output of the FIFO, while a read must destroy the old output andinsert the new input. The translator uses register writes for sequencing, so the standing moves on theirinputs are torn down. The translator generally uses a accept+ack at the input of each FIFO, with theacknowledgment releasing the next instruction codebag to execute.3.3 Arithmetic OperationsAddition and subtraction instructions are implemented using the Adder SHIP of IES31. Since IES31does not define a SHIP for multiplication or division, we constructed a new MultiplyDivide SHIP withtwo outputs. This SHIP has the ability to perform both signed and unsigned multiplication and division.For multiplication, the outputs are used for the upper and lower bits of the result, while for division, theyare used for the quotient and the remainder.2The output of the MultiplyDivide SHIP correspond exactly to what should be placed in the $hi and$lo registers upon executing multiplication and division in MIPS. This has a slight complication forsequencing, since the next instruction codebag cannot be released until the writes to both registers havecompleted. To accomplish this, we defined a TokenCombine SHIP that converts two tokens into one. Thewrite notifications are sent to this SHIP, and its output is used to release the next codebag.At the current moment, the translator does not check for arithmetic overflow in any of these instruc-tions.3.4 Logical OperationsThe Bitwise SHIP of IES31 allows any of 256 bitwise operations to be performed on the inputs. This isfar more than necessary to support MIPS, and since no one has yet implemented this SHIP, we defined anew Logic SHIP with support for the basic logical operations, such as and, or, xor, and nor.3.5 Shift OperationsMIPS assembly allows left, right arithmetic (i.e. with sign extension), and right logical (i.e. without signextension) shifts. The shift amount can be specified statically in the actual instruction, or dynamically ina register.IES31 defines a Shift SHIP that can perform various shifts of a single bit. This SHIP, however, appearsunsuitable for use with the MIPS instructions, since each
View Full Document
Unlocking...