An Overview ofFLEETCS-152FLEET• Brainchild of Ivan Sutherland• Fleshed out in collaboration with Berkeley graduate students• A one-instruction, clockless processor• Alternatively: an asynchronous transport-triggered VLIW machine• Designed to take advantage of asynchronous circuits• But first, I’d like to talk about...• Ancient bridges were made of stone• Required arch-and-keystone designSteel• Much stronger building material than stoneEarly Steel Bridges• Arch-and-keystone not required• Regardless, early steel bridges were built as imitations of stone bridges.Modern Steel Bridges• Steel made suspension bridges possible• Took a while for people to realize that new materials enabled new designsWhat does this have to do with Computer Architecture?• Synchronous circuits• Single-cycle, pipelined, superscalar, Tomasulo, etc• Asynchronous circuits• Early async processors imitated synchronous architectures• FLEET is a first draft of what “suspension bridges” might look likeCrash Course on Asynchronous CircuitsKLA• Kinetic Learning ActivityIF predecessor != successor THEN copy predecessorMuller C Element• Majority gate with output looped back• A two-voter election with “incumbent advantage” in event of a tieMC= =a01b00c1c1abc“majority”gateMicropipelines•Chain of Muller C-Elements•Each element connects to an inverted input on predecessor, non-inverted on successorCCCCMicropipelinesCCCC“each stage of the control...follows a very simple stage state rule:IF predecessor != successor THEN copy predecessor’s state ELSE hold present state[IES’89]MicropipelinesCCCCIF predecessor != successor THEN copy predecessor’s state ELSE hold present stateMicropipelines•Any “disagreements” propagate to the rightCCCCIF predecessor != successor THEN copy predecessor’s state ELSE hold present stateMicropipelines•Any “disagreements” propagate to the rightCCCCIF predecessor != successor THEN copy predecessor’s state ELSE hold present stateMicropipelines•Any “disagreements” propagate to the rightCCCCIF predecessor != successor THEN copy predecessor’s state ELSE hold present stateMicropipelines•Any “disagreements” propagate to the rightCCCCIF predecessor != successor THEN copy predecessor’s state ELSE hold present stateMicropipelines•Any “disagreements” propagate to the right•System is stable when pipeline contains•Zero or more agreeing stages•Followed by zero or more disagreeing stagesCCCCIF predecessor != successor THEN copy predecessor’s state ELSE hold present stateMicropipelines•Transition signaling•A transition on a stage’s output will:•Acknowledge data from the previous segment•Signal data ready to next segmentCCCCReadyAckDataOther Styles Exist• Too many for this talkAdvantages of Async• Average (not worst) case timing -- no “timing closure”• Early completion with some circuit styles• Separates correctness from performance• No clock tree• Low power• Better modularity• Better EMI profile• Extremely robust to variations Process, Temperature, VoltageCaltech MiniMIPSDesigned 1995-1998250% the performance of the best synchronous MIPS on the same fabrication processPerformance scaled “automatically” with voltage and temperature changes 0 50 100 150 200 250 1 1.5 2 2.5 3 3.5 4 4.5 5MIPSvoltage"foo.dat"Communication Matters• “Metal rod” model of VLSI wires• Communication is what matters, so put the programmer in charge of it• One instruction: MOVEMike Holenderski’sAnimationhttp://research.cs.berkeley.edu/class/fleet/docs/fleet_animation.swfMIPS Pipeline vsFLEET SHIPsPC+4rtrsrdregistersALUDatamemoryimmdecodeInstructionMemoryInboxes and OutboxesAM11: Data/Token In/Out BoxesThe Students and Instructors of CS-294-11edited by Adam MegaczNovember 18, 20061 Inboxes and Outboxes for TokensAs an amendment to earlier memo AM10, formerly “bare” token inputs andoutputs now have inboxes and outboxes.In the diagram below, dashed lines indicate connections which always carrytokens, while solid horizontal lines carry data in the case of data in-boxes/outboxes and tokens in the case of token inboxes/outboxes:OutBoxDataInAckDataOutTriggerOutbox Client ShipSwitchFabricInBoxDataInAckDataOutInbox Client ShipInstruction InstructionInboxes and OutboxesToken inboxes and outboxes behave in a slightly different manner than datainboxes and outboxes. The following large chart shows the 24 generalized in-struction forms; the four charts following it depict which instruction forms arevalid for each type of box.1Code “Bags”• Unordered sets of instructions• Lets us start fetching the next “block” of code as soon as the current “block” starts executing• Unlike sequential-instruction ISAsAnatomy of a FLEET Instruction2 Instruction OrderingRecall that if a codebag contains two or more instructions which have the samesource address, those instructions are guaranteed to be executed at their sourceship in the order in which they appear in the codebag.This property is important for understanding the usefulness of some instruc-tion forms. In particular, many instruction forms are only useful as a “barrier”in the stream of instructions being sent to a particular ship.3 Instruction FieldsAn instruction tells a box what action to take. This action involves possiblycopying or consuming a datum from its input and possibly sendingthat datum on its output. The instruction may also specify whether ornot the box must wait for a token on its input before performing thisaction, and whether it should emit a token on its output to announce thatthe action has been completed.The field (formerly ) can now hold only values and∞. A is no longer valid; its role has been subsumed by the otherinstruction fields.A conceptual Fleet instruction format is shown below.SourceAddressTriggeredDataInIgnore/Copy/TakeCountDestinationAddress1.5log MAXMOVE2log NUMSOURCES2log NUMDESTINATIONS21Ack1DataOut1Anatomy of a FLEET InstructionNote that the bits need not occur in this order. Indeed, the bits are likely to becoded more efficiently, since the field has three possible values, and notall combinations of , , , and are valid.The new fields include:•If set, the box will wait for a token on its input and consume itbefore taking action.•If set to , the box will not wait for a value to arrive on itsinput before taking action. If set to , the box
View Full Document