Turing-inspired scripting language simplifies simulation complexity

Current simulation languages are primarily libraries built on top ofprogramming languages such as C++, Python, Java and Tcl. Themodeler or architect must be conversant with the semantics and codingstyles of these languages, in addition to understanding the systemoperation. Some can be extremely complex such as the object-orientedsemantics of C++ and others will be complex mechanisms to createscheduled events such as Tcl/TK.

However, the use of the modeling-specific scripting language, calledSmartMachine that draws on concepts developed for the original Turing Machine can beused to overlay popular simulators such as SystemCand Ptolemy. This makes itpossible to more easily construct and generate statistics for queuing,co-design and algorithmic models.

The simulator addition enhances the chosen simulation programminglanguage to provide concurrency definitions, advanced data types andbasic operations such as priority queue, scheduling schemes andstatistics generator. It has been used in modeling a variety ofapplications including a functional cache, the FlexRaybus protocol, hardware schedulers and RTOS models.

Current simulation languageapproaches
Current simulation languages are stand-alone and integrated into thedesign flow. A large part of the system must still be defined using thestandard language constructs. For complex activities, such assemaphores and thread management, the code required can only bedeveloped by experienced programmers. In addition to system modelingbackground, these engineers need to be very good software programming.

The primary issue with simulation languages is the difficulty increating models. These languages are introduced to make simulations runfaster or for creating standards, but they take much longer toconstruct relative to the solutions being replaced. So, all thesimulation performance benefits are lost to the model constructiontime. The SmartMachine addresses this by providing a small set ofinstructions and an integrated regular expression language. Models canbe constructed using only these instructions and are as such readableby non-modelers.

Current programming simulation languages do not provide the ease ofuse requirement for wide adoption and lack such features as easyparameterization for repetitive runs, accessing modeling memories andgenerating scheduled events. Standard functions such as data typetransformation, defining queues and arrays and complex regularexpressions need to be built custom.

The model and the simulation code must be valuable beyond just themodeling world. It must be the basis for generating documentation anddebugging implementation. To debug a signal problem in theimplementation, the engineer could quickly refer to the system model.To be usable as a documentation tool, IP code has to be simple.

Code structure with well written code is possible, but visibilityinto structure in code is very difficult with existing approaches.Graphical block diagrams are incredibly effective for seeing patternsand can quickly identify problems that are almost impossible to figureout from code. A code that is built state-machine like and isprocedural would be very quick for tracing and equal understanding byall.

The Turing Machine Advantage
Alan Turing createdthe “Turing” machine in 1936, based on a finite state machine thatseparates information into two elements, its internal state andexternally derived state. At any instance of time, the state is basedon its current state and the next discrete time step.

A “Turing” machine reads its input from a tape it is processing. Thetape controls the behavior, based on the current state, and determineswhat action to take next (erase, write or move tape). Any particularTuring Machine can be described as an action table, or as statetransition diagram, representing the same information in diagrammaticform.

The advantage of the Turing Machine is in its ability to storeinformation to a tape of unlimited length, storage for partialexecution results, and room for unlimited output. With the properinformation on a tape (or script), a Turing Machine could emulate theactions of a different machine. The ultimate Turing Machine would beable to read any set of instructions from its tape.

Turing proved that such a machine, the Universal Turing Machine,would also be a universal computer, that is, it could emulate anymachine whose behavior could be described symbolically. Turing assumeda conventional model of computation, meaning a distinction betweenfixed data and variable data, which a computer could operate on. TheTuring Machine is considered the simplest form of generic processor. ATuring Machine has three commands and a simple state machine.Theoretically, a turning machine can perform any operation given aninfinite tape.

The SmartMachine Difference
Similar to the Turing concept, the SmartMachine is like a tape thatmoves back and forth, with state machine like decisions. But unlike theTuring machine, this approach uses addresses, instead of a tape, andJump-If-True, Jump-If-False and While are instructions that describethe decisions.

The SmartMachine is (1) closerto implementation, (2) morestate-machine like, (3) handles threads easily and (4) workson memories. The scripting language consists of 10 instructions, 40keywords and a Just-In-Time compiler. The concept behind using areduced instruction set is that users can learn how to create a modelusing a custom, small instruction set scripting language quickly, asopposed to a general-purpose complex language.

Each script line can be indexed with an address and should be easilyunderstood by hardware or software architects alike. The simplifiedinstruction set also has the advantage of a simpler JIT compiler, andfast execution, much like RISC architecture, except it is done insoftware.

The blocks compile the script at run-time and execute within asimulation kernel. The language can describe dynamic functional andperformance details of components, algorithms, implementations andsub-systems. The language has an extendable Regular Expression Languageand creates classes of the script-instance with the optimized (JIT)compiler.

The scripting language uses the Just-In-Time compiler to acceleratesimulation performance by 10-100X over existing scripting languages.The instructions, integrated operations and the Regular ExpressionLanguage reduce modeling time by over 6X relative to standardsimulation languages. Other scripting languages, such as Tcl/Tk, Perland Python, offer a limited set of similar functionality outside asimulation environment and tend to execute slower.

The SmartMachine has ten instructions:

DEF    Declare, or define, a memory
LBL     Labelused as identifier by other instructions
END    End stopscurrent thread and removes from Process Queue
ACT     Actioninstruction for expressions, queue operation and scheduling a wait
JIT      Jump if True is an if expression that responds to a true result andjump to an 
             instructionline based on a LBL or absolute address
JIF      Jump if True is an if expression that responds to a false result andjump to an
             instructionline based on a LBL or absolute address
WHL   While (evaluates totrue) executes a set of instructions following this statement
             until aRTN command is reached, Else (evaluates to false) jump to aninstruction
            line based on a LBL or absolute address
SBR     ExecuteSubroutine at an instruction line based on LBL or absolute address
RTN     Returnto the SBR or WHL statement that corresponds to this Return
GOTO  An instruction linebased on a LBL or absolute address
GTO     Threadis a special case of the Goto that initiates a new Thread while the
             current  Thread continues.

The user defines code in a fixed procedural format for the JITcompiler as shown in Table 1, below.

Table1:SmartMachine Procedural Format

Basic SmartMachine Operation
Figure 1 below illustrates theunderlying block diagram for the SmartMachine. The Just-In-Timecompiler is not shown in diagram. The script engine communicates withmodel memory as block, local, or global types. The script memory isknown only to a specific instance of script.

Figure1: SmartMachine Block Diagram

Using this block, the user can have multiple SmartMachine blocksrunning the same script with no memory name overlaps. The local andglobal memory can be accessed across multiple scripts instances.

The memories can be used to define priority queues, array queues,FCFS (First Come First Served) queues, array memories, scheduler links,or make virtual connections. The simulator-level integration of thisscript language leverages legacy models in the existing simulationenvironment. Moreover, the underlying regular expressions commands canbe executed for complex operations.

The script engine also communicates with the Input_Queue ( In Q, in Figure 1 ) , Wait_Queue ( Wait Q, in Figure 1 ) , and Process_Queue (Thread Q, in Figure 1 ) .

A user can add as many input and output ports to the script instanceas required. The Data Structures arriving on the Input Port enters the Input_Queue . The “wait” statementscan be executed in SmartMachine to either wait for a specified time orfor a Data Structure (event) on an input port.

The name assigned to an input or output port, can be used in thescript to retrieve Data Structures from an Input, or send DataStructures to an output. The SmartMachine can also communicate withother script instances and with other named memory locations that arevisible from the script using a named connection.

Data Structures can be transferred virtually anywhere within thesimulation model using this feature. The Input Queue contains DataStructures arriving on the input port(s), directly through virtualmemory connection(s), or from internal thread functions.

The Wait Queue is populated with the Command Address and the threadwhich is waiting for an external event. The Thread Queue contains thelist of the different threads currently executing. Thus, if a thread iswaiting for an input event to continue processing, then the thread willbe in the Wait Queue. Once an event arrives, the waiting thread will bemoved to the back of the Thread Queue for execution.

Figure2: SmartMachine script for an M/G/1 queue model of a Bank Teller

The example script above in Figure2 shows the construction of a Bank Teller Line defined as aM/G/1 queue (exponentially distributed inter-arrival times and anarbitrary distribution for service times) using the Input_Queue and theSmartMachine instructions. The instructions are used to generatecustomer arrivals at a Bank Teller. The customer arrival rate is basedon the selection of the distribution parameter in the graphical entry.

The SmartMachine is shown integrated into VisualSim, an architectureexploration simulation environment from Mirabilis Design. The outputhistogram of the script for the different distribution selections isshow in Figure 3 below .


Figure3. Histogram output from SmartMachine script plotted in VisualSim PostProcessor

Conclusion
A modeling-specific Turing Machine that executes a script with 10 typesof instructions, SmartMachine combines the power of custom-code withgraphical modeling to create a highly productive modeling paradigm forsolving complex problems.

There are many applications that can take advantage of theSmartMachine, especially where the model schematic size and simulationspeed are a consideration, including:

* SoftwareEstimation
* HardwareRefinement
* Real TimeOperating System
* Protocol StateDiagrams
* Switch Fabrics
* Algorithm Analysis
* Advanced Statisticsgeneration
* Complex FunctionalExpressions
* Multi-threadedapplications

The advantages of this approach are ease-of-learning and use, nativecode speed simulation performance, small code footprint and languageflexibility. Modelers can author blocks for reuse by others.

Deepak Shankar is Founder/CEO and Darryl Koivisto is CTO at MirabilisDesign Inc.

Reference:
[1] “Computing Machinery andIntelligence” ” Alan Turing, (Mind, 1950).

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.