%
% HiPAAC Submission guidelines and sample document in LaTeX
%
\documentclass[times, 10pt,twocolumn]{article}
\usepackage{hipaac}
\usepackage{times}
%\documentstyle[times,art10,twocolumn,hipaac]{article}
%-------------------------------------------------------------------------
% take the % away on next line to produce the final camera-ready version
%\pagestyle{empty}
%-------------------------------------------------------------------------
\begin{document}
\title{Hardware Support for .NET MicroFramework CLR Components on FPGAs}
\author{Sneha. M\\
College of Engineering, Guindy\\Anna University \\
Chennai 600025 ,India\\ sneha.magapu@gmail.com\\
% For a paper whose authors are all at the same institution,
% omit the following lines up until the closing ``}''.
% Additional authors and addresses can be added with ``\and'',
% just like the second author.
\and
jgdhjsgdhsjg\\
Institution2\\
First line of institution2 address\\ Second line of institution2 address\\
SecondAuthor@institution2.com\\
\and
}
\maketitle
\thispagestyle{empty}
\begin{abstract}
Microsoft introduced the .NET technology, which brings the power and reliability of managed code
to scale from large servers to embedded devices. To serve the market for even smaller devices,
Microsoft has developed a new platform Microsoft .NET Micro Framework (.NET MF). A .NET MF
embedded processor has been designed on FPGAs based on a hardware-softwar co-design method with
hardware support for specific components of the MF CLR.The scope of the project is to diversify the features
supported by interpreters specifically designed for the embedded domain. For a reconfigurable and flexible design,
the Field Programmable Gate Array (FPGA) is taken as the target technology for the .Net MicroFramework processor.
\end{abstract}
%-------------------------------------------------------------------------
\Section{Introduction}
From sensor networks to smart watches, there are new applications that require low hardware cost and low power
consumption, but would benefit from the flexibility, reliability, code reuse, and great tools of .NET. The .NET
MicroFramework is designed to work on devices where hardware capabilities are too limited to be practical with
the full .NET or .NET Compact Framework running on Windows XP Embedded or Windows CE.
With the proliferation of embedded devices, the system design paradigm has shifted from the conventional design
to hardware-software co-design. The focus is on building customized hardware and software. The hardware
customization has been facilitated by Field Programmable Gate Arrays (FPGAs). FPGAs, which are reconfigurable,
provide a faster execution environment in addition to low initial cost and minimal usage of silicon space. FPGA
is an array of logic gates that can be hardware-programmed to implement user-specified tasks. Using FPGAs,
one can devise special purpose functional units that may be very efficient for some limited task. It is also possible
to customize the entire instruction processor using these devices. As FPGAs can be reconfigured dynamically,
it is possible to design customized systems for more complex special tasks at speeds that are higher than what
can be achieved with general-purpose processors.
The paper is organized as follows. Section 2 discusses the past trend regarding the design of virtual machines, and
about the related work going on. Section 3 introduces the .NET MicroFramework, the CLR and its components.
Section 4 highlights our design of the CLR. Section 5 details about our scheme of implementation. Section 6 gives the results.
%-------------------------------------------------------------------------
\Section{Related Work}
The field of virtual machines (VM), and language-independent and platform-independent execution environments has always
fascinated language designers and implementers for a long time. Such implementations have a lot of advantages over the native
compilers strategy, the main objective of adopting such an approach being portability. Portability is achieved by having the high
level code translated to an intermediate form, which a system, usually called the Virtual Machine, translates to the native code of the
target architecture. The virtual machine is a software implementation that lies between the application and the operating system. Or
in other words, the VM can be thought of as a program that can run other programs. One of the ways of realizing such a virtual Machine
system, and the widely adopted one, is by modeling the VM as a stack. The reason for adopting a stack-based architecture is that, any
virtual machine, which aims to achieve portability across platforms, cannot make assumptions on the underlying architecture. A stack,
on the other hand can offer higher level abstractions and abstract actions can be specified on a stack (push, pop, addtop- two etc.). Thus,
it becomes desirable to model VMs as abstract stack machines.
The intermediate code form for Java is the Byte code, and the execution environment is called Java Virtual machine. Many advances have
been done to increase the speed of execution. One way to achieve faster runtime is to have dedicated java coprocessors or to have specific
processors( Java Processors) that can execute Byte codes. There have also been complete FPGA implementations of JVM[5].
.NET is an upcoming technology that is now given attention by embedded systems groups and reconfigurable computing groups. There is a
chip that is capable of running a very restricted subset of the CLR but the scope of the application is pretty narrow. An implementation of the .
NET CLR Execution engine has been done on FPGAs[1]. But this implementation of the execution engine supports a set of basic instructions
such as arithmetic, logical and comparison instructions. The engine has been modeled as a stack based machine, the stack being maintained in
the hardware. The CLR engine runs on the MicroBlaze softcore processor provided by Xilinx specially for FPGAs. We aim at enhancing the execution
engine and providing hardware support for the other features of the CLR.
SPOT (Smart Personal Object Technology) is Microsofts new entrant in embedded device technology, for task specific devices. It is, in a nutshell,
a device based on "Ollie" - a 32-bit ARM7 processor core that runs a very, very stripped down Windows OS. Right in the processor is a very scaled-down
Common Language Runtime (CLR) known as TinyCLR. What sets SPOT apart is that it leverages the Rapid Application Development (RAD) capabilities
Microsoft provides through managed code and Visual Studio 2005. The TinyCLR has an even smaller footprint than what Windows CE offers, and is designed
for devices with limited resources and functionality.
%-------------------------------------------------------------------------
\Section{The .NET MicroFramework}
The .NET MicroFramework supports a subset of the .NET Framework and runs with or without an underlying OS. So the footprint is smaller. Current configurations of the MicroFramework require about 300K of RAM. The MicroFramework provides a subset of full OS features, so it does not require an OS and is referred to as a bootable runtime. Making the runtime bootable means that booting support, interrupt handling, threading and process management, heap management, and other environmental support functions that are typically provided by the operating system have been added to the .NET MicroFramework so that it can run directly on hardware. The OS services that are needed by the application are provided up through the runtime. In creating a bootable runtime, the .NET MF provides a subset of the OS features directly rather than relying on the underlying OS, the subset being selected as services required to run applications on small devices.
The Common Language Environment (CLR) is the run-time environment of the .NET framework. It manages the execution of code and provides services that make the development process easier. The intermediate code form of the .NET system is called Common Intermediate Language (CIL) or the Microsoft Intermediate language (MSIL). The .NET Microframework CLR is a small, optimized managed code runtime based on industry-standard ECMA specifications. When native code executes, the operating system really doesnt know anything about the code and therefore can only execute it blindly. Managed code includes a great deal of information about the code so that the CLR can prevent errors.
.NET MicroFramework CLR implements all of the major features found in the full CLR. It omits a few features that were deemed inappropriate for this class of device, and adds a few features that are specific to this class of device. The Micro Framework CLR supports major features like Exception handling, time sliced thread management, Garbage collection and defragmentation of memory.
%-------------------------------------------------------------------------
\SubSection{Execution Engine}
As with all managed code runtimes, the .NET MicroFramework CLR provides a virtual machine abstraction that is targeted by the compiler tools from the source programming language. In order to execute programs, a special engine is required to load, prepare, and perform the instructions specified in the program (the Intermediate Language [IL]). One of the key benefits of this design is that it allows for code to be developed independently of the actual hardware on which it runs. Since programs are specified in terms of a virtual machine, the execution engine must translate encoded operations into native operations (i.e., instructions that can be performed by actual hardware).
There are two basic approaches (and a myriad of variations) to accomplish this: interpret the code as it is executing or compile it to native code, as it is needed (Just In Time [JIT]). .NET MicroFramework CLR interprets program code.
%-------------------------------------------------------------------------
\SubSection{Exception Handling}
One of the keys to creating a safe execution environment is the ability to effectively handle exceptional runtime situations, which might occur as a result of unforeseen operating conditions. Applications are allowed and encouraged to use the exception handling mechanisms found in traditional .NET programs. The execution engine manages the dispatching and clean up associated with exceptions. In addition, it has special mechanisms for protecting the integrity of the system as a whole from unruly programs, by gracefully cleaning up state that could be causing a program to misbehave. Ultimately, a program will be blacklisted if it continues to fail according to a pre-determined heuristic.
%------------------------------------------------------------------------
\SubSection{Garbage Collection}
In .Net MicroFramework which is specifically designed for specialized hardware devices, memory management is tied to the type system, making it possible to track memory at the object level. This allows the system to reclaim dead objects and removes this burden from the programmer. In addition, memory can be compacted to create contiguous free space for newly allocated objects, thereby avoiding out of memory conditions due to heap fragmentation. This is known as Garbage Collection (GC).
Every program uses resources of one sort or anothermemory buffers, screen space, network connections, database resources, and so on. In fact, in an object-oriented environment, every type identifies some resource available for your program's use. To use any of these resources requires that memory be allocated to represent the type. The steps required to access a resource are as follows:
1. Allocate memory for the type that represents the resource.
2. Initialize the memory to set the initial state of the resource and to make the resource usable.
3. Use the resource by accessing the instance members of the type (repeat as necessary).
4. Tear down the state of the resource to clean up.
5. Free the memory.
Although the above paradigm seems very simple, freeing memory when it is no longer needed or attempting to use memory after it has been already freed are two important concerns. In .Net, the developer can use certain methods for explicitly cleaning memory.
%-------------------------------------------------------------------------
\SubSection{Multi-threading}
.NET MicroFramework CLR provides multi-threading support, even when the underlying platform does not. While not a true multi-threaded kernel, the execution engine simulates one by offering time-sliced context switching using 20ms quantum. Threads are prioritized and interruptible (due to instruction level interpretation hardware).
%-------------------------------------------------------------------------
\Section{Design and Implementation}
We intend to provide hardware support to the .NET MicroFramework Common Language Runtime for embedded systems (CLR) on FPGAs so that programs targeted to run on CLR software engine are accelerated. The system is to be built atop the MicroBlaze softcore processor, which will run on a Xilinx FPGA board.
The very common solution to build any general VM is to have it as an interpreter and/or a JIT compiler or an AOT compiler. This kind of a software solution is relatively easier to build and cost effective, but it compromises on the performance. But the price they demand is flexibility. Moreover, complexity and cost are high for such an approach. Our objective is to exploit the advantages of both these approaches by employing both of them. In other words, we propose a co-design sort of an approach to achieve a better negotiation between cost and performance. Also, with this paradigm lies flexibility too. A goal of the co-designed CLR is to achieve better performance over a pure software solution. The hardware partition of the co-designed CLR is proposed to work in unison with the host processor, which can be a GPP (which in our case happens to be a softcore). The choice of an FPGA provides a development environment for easily shifting the partitioning between hardware and software to arrive at an optimized solution, and the flexibility to fit the design into targets of different sizes. Fig. 1 gives the overall block diagram of the system.
\begin{figure}[h]
\caption{Overall design of the built system}
\end{figure}
// Fig 1 of thesis
Since the CLR engine is implemented using a hardware stack, handling stack overflows is of prime importance. The stack overflow problem is handled using a spill fill handler.The stack is a 16-entry stack and is configured in the hardware.
%-------------------------------------------------------------------------
\SubSection{Interpreter (Software)}
The MF CLR interpreter is a software application that runs on the custom hardware. The engine runs infinitely, reads the MSIL code, as and when it reads the opcode it decodes it and sends command to the respective functional for the operation and then the final result of the execution is obtained.
while(moreInstructions())
{
switch (next_instruction())
{
case instn1:
instn1();
break;
.
.
case instnN:
instnN();
break;
}
}
All the HLL programs get translated to an intermediate form called a .NET assembly which can either be a DLL or an executable. The executable assemblies are Portable Executable (PE) files in which the MSIL instructions are encoded, and then interpreted by the CLR. As mentioned above, metadata gets packed with an assembly, which is made use of by the CLR during the interpretation stage.
From the PE input, a few of the initial parameters are obtained which include entrypoint token, indices to method table, typedef table, field table to handle the method calls and obtain the details about the object references, local variables, arguments to methods for calling the methods and performing the interpretation. At any instant, to perform any operation the operands will be available on the stack or in the data register of the stack, so the hardware stack will suffice for this.
%-------------------------------------------------------------------------
\SubSection{Interpreter (Hardware stack)}
The hardware stack is a 16 entry 32-bit circular stack. The hardware also includes two temporary registers (A and B), which act as source registers for the functional units. For any binary operation to be performed the 2 entries from the top of the stack are required and they are stored in the above registers in every clock cycle so that any operation required will be immediately done in the next clock cycle.This way, the overhead of pops will be minimized for each function to be performed. As A and B are updated in every clock cycle, any changes in the top two positions of the stack will be automatically reflected in them.. Fig 2 describes the hardware components.
// Fig 4 of Review3.doc
\begin{figure}[h]
\caption{Hardware system design}
\end{figure}
The operation of the stack is modelled as a state machine described in detail, in Fig 3.
// fig 6 of thesis
\begin{figure}[h]
\caption{State machine of the entire operations of the stack}
\end{figure}
%-------------------------------------------------------------------------
\SubSection{Spill fill handler}
The stack spillfills are handled by the spill fill handler unit in hardware. The detailed design of the spill fill handler unit is as shown in Fig 4. The stack is a 16-entry circular stack and the backing store is a 128 entry linear block maintained in memory.
\begin{figure}[h]
\caption{Detailed design of Spillfill Handler}
\end{figure}
// Fig 3 of thesis
The operation of the spill fill handler is also designed as a finite state machine that operates in parallel with the stack machine. As the stack is a circular one, a rear pointer is maintained. The rear and stack pointers define the conditions for spilling and filling. The backing store is maintained in the external RAM. Spilling of the stack is done when the stack becomes full. During spilling, half of the stack is spilt. The spilt entries are refilled during filling, which happens when the stack becomes empty. When elements are present in both the stack and the backing store, the machine is in the stack and bstore state when the hardware stack and the backing store are considered to be a contiguous stack as a whole.
%-------------------------------------------------------------------------
\SubSection{Garbage collecor}
Garbage collection is used to free the unfreed objects that are irrelevant to the current context. The heap is be divided into fixed size pages. There is a Next Object Pointer which keeps track of the next available free page for the objects. A free table is maintained in hardware for every entry correspondingly in the heap space. The heap manager maintains the next free entry in the heap and the heap size. The detailed design for the garbage collector is given in Fig 5
\begin{figure}[h]
\caption{Garbage collector}
\end{figure}
// Fig 4 of thesis
The logical operations of the garbage collector are given in Fig 6
\begin{figure}[h]
\caption{Operations of the garbage collector}
\end{figure}
// Fig 8 of thesis
In the first phase, the global function level is set during every call to a function and the function level for every object allocated is also remembered. After a new object is allocated in the heap, next_free_heap is allocated to the next free entry in the heap. In case the heap is full, indicated by the index returning to the earlier position, then garbage collection takes place. Now, those objects whose function level value is less than the current function level are dead objects and they will be collected.
%-------------------------------------------------------------------------
\SubSection{Exception handler}
The Exception handler is included to handle all exceptions that the execution engine might encounter. The handling is done in two passes. In the first pass, the RVA (Relative Virtual Address) of every function along with the handler address is stored in the exception table, maintained in the memory. In the second pass, if an exception occurs, the handler address is taken from the table and the control goes to the handler.
// Fig 5 of thesis
\begin{figure}[h]
\caption{Working of Exception handler}
\end{figure}
%-------------------------------------------------------------------------
\Section{Performance}
The system was tested on a Xilinx Virtex II Pro FPGA Board. This board has a 300MHz softcore MicroBlaze processor which is a 32-bit big-endian processor. The board has a 32KB on-chip memory and a 256MB off-chip DDR memory. A .NET PE is given as a input to the CLR engine. After identifying the initial entry point, the CLR engine works asynchronously with the hardware to execute the PE. The CLR prints the stack trace of the executable as each instruction is executed. The output can be seen in the HyperTerminal.
The performance enhancements that were obtained using the system are highlighted in the following.
%-------------------------------------------------------------------------
\SubSection{Execution time}
The execution times of the codesigned CLR and the pure software CLR are compared using flat profiling. The results are tabulated in Fig 8
Speed Up Factor = Execution time Pure Software / Execution Time Co-designed
// fig 5.8 from seniors thesis
\begin{figure}[h]
\caption{Profiling results}
\end{figure}
From the above figures, the average speed up factor is found to be 1.89. Thus it can be concluded that the performance of a co-designed .NET processor is better than a pure software solution. This vindicates our aim that a hardware implementation is better than a pure software approach.
%-------------------------------------------------------------------------
\SubSection(Robustness}
The limitations of smaller stacks in the earlier implementations have been overcome because of the availability of the large backing store. In implementations that do not have a spill fill handler, stack overflows are not handled and hence requests for any further operations with the stack are refused. Generally heap size is limited in embedded devices and hence dead objects have to be collected as garbage. Thus this implementation supports for more objects in each function level. As exceptions are handled, it eliminates unnecessary termination from the program and also avoids threats to the system.
%-------------------------------------------------------------------------
\Section{Conclusion}
Many embedded devices are too small to support the full .NET Framework. Also, they dont need the entire functionality that the .NET Framework provides. The .NET Micro Framework provides a small, efficient implementation of the .NET runtime for smaller devices. Enhancing that with hardware support has great advantages to developers in terms of performance, speed and portability. Our implementation of the .NET MicroFramework CLR is a hardware-software combination, comprising of the execution engine and the other constituents of the CLR (garbage collection, thread management, exception handling). The codesign approach lends enhanced performance to this hardware supported CLR as compared to the existing pure software implementation. The advantages and limitations of this approach are analyzed.
%-------------------------------------------------------------------------
\Section{Future work}
Future enhancements can be done to make the existing design perform better. Firstly, the system may be extended to support more types like float, string etc, which will make the system more versatile. Secondly, the hardware may be made more suitable for the execution of object modeling instructions in hardware. But the hardware complexity must be kept in mind so that it doesn't become a bottleneck in itself. The design can then be extended to perform better for specific embedded systems by optimizing specific features of the design such as the stack cache and extending the functional units to perform a extended set of operations specific to an embedded system. Finally, the system can be modelled to be less hardware dependent, i.e, the hardware partition may be designed to be more powerful and self-contained.
%-------------------------------------------------------------------------
\nocite{samp1,samp2,samp3,samp4,samp5,samp6,samp7,samp8}
\bibliographystyle{hipaac}
\bibliography{hipaac}
\end{document}