Package at.dms.kjc.backendSupport

Package documentation for at.dms.kjc.backendSupport

See:
Description

Interface Summary

ComputeNodesI<CodeStoreType extends ComputeCodeStore<?>>	Define what a collection of ComputeNodes must implement.
Layout<T extends ComputeNode>	A Layout makes the association between a ComputeNode and a SliceNode.

Class Summary

BackEndFactory<ComputeNodesType extends ComputeNodesI<?>,ComputeNodeType extends ComputeNode<?>,CodeStoreType extends ComputeCodeStore<?>,ComputeNodeSelectorArgType>	Factor out parts of back end that need matching types.
BackEndScaffold	Create code for a partitioning of Slices on a collection of ComputeNodes.
BasicGreedyLayout<T extends ComputeNode>	Use greedy bin packing to allocate slices to compute nodes.
BufferSize	Centralize calculation of buffer sizes
Channel	A Buffer is an implementation of an Edge in a back end.
ChannelAsArray	Channel implementation as an array.
ChannelAsCircularArray	Implement a channel as a circular array.
CodeStoreHelper	For creation of additional code necessary to getting filter / joiner / splitter code hooked up to a ComputeCodeStore.
CodeStoreHelperJoiner
CodeStoreHelperSimple	CodeStore helper routines for FilterSliceNode that does not need a peek buffer.
CodeStoreHelperSplitter
CommonPasses	Common passes, useful in new back ends.
ComputeCodeStore<ComputeNodeType extends ComputeNode<?>>	A data structure for associating code with each compute node at each phase.
ComputeNode<StoreType extends ComputeCodeStore<?>>	This abstract class represents a device that can perform computation.
ComputeNodes<CodeStoreType extends ComputeCodeStore<?>>	A ComputeNodes is a collection of ComputeNodes.
DelegatingChannel	A Channel that delegates all useful work to another channel.
DumpSlicesAndChannels	Dump a graph with info about slices and channels.
EmitCode	Takes a ComputeNode collection, a collection of Channel's, and a mapping from Channel x end -> ComputeNode and emits code for the ComputeNode.
EmitTypedefs	Emit code defining the vector types and structure types used in the program.
FilterInfo	A class to hold all the various information for a filter.
GetOrMakeChannel	Create channels of appropriate type for a back end.
MinCodeUnit	Minimum usable implementation of SIRCodeUnit interface.
MultiLevelSplitsJoins	This pass will break up splits or joins (OutputSliceNodes and InputSliceNodes) that are wider than the number of memories attached to the chip.
NoSWPipeLayout<T extends ComputeNode,Ts extends ComputeNodesI>
ProcessFilterSliceNode	Process a FilterSliceNode creating code in the code store and buffers for connectivity.
ProcessInputSliceNode	Create kopi code for an InputSliceNode.
ProcessOutputSliceNode	Create kopi code for an OutputSliceNode.
SpaceTimeScheduleAndPartitioner	Extend BasicSpaceTimeSchedule by storing a partitioner.
UnbufferredPopChannel	A Channel with the single purpose of holding the name of a pop() routine.
UnbufferredPushChannel	A Channel with the single purpose of holding the name of a push() routine.

Enum Summary

SchedulingPhase

What phase of Slice graph scheduling is a bit of code generation associated with? This enum should tell: initialization, pump priming for software pipelining, or steady state.

Package at.dms.kjc.backendSupport Description

Package documentation for at.dms.kjc.backendSupport

For information about using the classes in this package for adding a new back end, please see adding-a-backend.

The backendSupport package was refactored from the spacetime back end.

Back end support has several phases:

• Standard transformations and optimizations:
  CommonPasses takes the data passed to the back end from StreaMITMain, performs a standard suite of optimizations on the stream graph (see at.dms.kjc.sir.lowering), and converts to an unstructured graph format (see at.dms.kjc.slicegraph.

  If you have a new optimization, the place to put it is usually in CommonPasses so that it is available for all back ends.

• Laying out code on your collection of processors:
  This package supplies several methods of performing layout: a greedy method BasicGreedyLayout and a method using simulated annealing NoSWPipeLayout. Both methods assume that there is an estimate of work per filter. So far, we only have work estimates for the raw processor. Both methods assume that all processors are interchangeable. If this is not the case, it is not too difficult to subclass NoSWPipeLayout. (BasicGreedyLayout needs to be enhanced to support limiting the placement of a filter to a particular subset of the processors.)

• Lowering to Kopi code:
  This is where most of the code in this package is used. See adding-a-backend for description of steps.

  The code for each filter has its push, pop, and peek expressions replaced with calls to communication code stored in Channels. The code for filters, and generated code for splitters and joiners is stored in ComputeCodeStores. ProcessFilterSliceNode handles the translation of filters and storing code into ComputeCodeStores; CodeStoreHelperSimple wraps the translated code with scheduling code (including some scheduling action on channels). Similarly, ProcessInputSliceNode and CodeStoreHelperJoiner create code for, and wrap scheduling code for at.dms.kjc.slicenode.InputSliceNodes. ProcessOutputliceNode and CodeStoreHelperSplitter create code for, and wrap scheduling code for at.dms.kjc.slicenode.OutputSliceNodes. These classes have some predefined extension points, and can be sub-classed as needed.

  Sub-class BackEndFactory to define your processor type (subclassing ComputeNode), your system as a whole (implementing ComputeNodesI or subclassing ComputeNodes). You can add extra bits of code generation to a subclass of ProcessFilterSliceNode etc. for general extension, or add processor-specific bits of code generation to a subclass of ComputeCodeStore. All of the subclasses can be assembled in a way in which they can reference each other by subclassing BackEndFactory.

  BackEndScaffold contains the routines to drive the generation of Kopi code for each SliceNode. It drives the ProcessFilterSliceNode code etc. based on a schedule SpaceTimeScheduleAndPartitioner. The schedule has three phases, enumerated in SchedulingPhase. Both the INIT and PRIMEPUMP phases generate code into the initialization portion of a ComputeCodeStore. The STEADY phase generates code into the steady-state portion of a ComputeCodeStore. (There is also a cleanup portion of a ComputeCodeStore that is currently used only for closing at.dms.kjc.sir.FileWriters.

• EmitCode creates C code from the Kopi code contained in the ComputeCodeStores and the Channels. Since each processor type seems to require a slightly different top-level main function, there is no provided top-level main.

  EmitTypedefs will create some C code that is commonly stored in a .h file. You will probably want to use some additional code to package whatever else you need into the .h file

Channels

Channel has many subclasses.

GetOrMakeChannel should be subclassed to create channels of the appropriate subclass of Channel. It defaults to using arrays to implement channels, which should work for intra-processor communication. You will probably want to override makeInterSliceChannel to handle inter-processor communication.

The following subclasses of channel are implemented for intra-processor communication

• UnbufferredPopChannel and UnbufferredPushChannel have no underlying data structure and are used to communicate directly between filter code and joiner (resp. splitter) code.
• DelegatingChannel has no underlying data structure and is used for trivial splitters and joiners to pass requests for action on a channel directly to the channel implementing the InterSliceEdge.
• ChannelAsArray provides an array implementation of a buffer that is completely filled by the producer and completely emptied by the consumer.
• ChannelAsCircularArray provides an implementation as a circular array of size 2^n that may contain residual data between one execution of the consumer and the next.
• There is no implementation yet that is suitable for large structures or arrays over channels when there is residual data between one execution of the consumer and the next. In this case, rounding up to a power of 2 may cause excessive space use.
• BufferSize is used to determine the minimum size for array implementations of channels.

Passing arrays over channels is a nuisance when it comes to generating working and efficient C code, since C has inadequate support for array dimensions. One idea for fixing this is to use Channel#assignFromPeekMethod() and Channel#assignFromPopMethod() to copy arrays directly into local variables. NB: this needs support in the channel implementations and in EmitCode.