Transcript Operating System Support for RCS

Operating Systems for
Reconfigurable Systems
John Huisman
ID:0208506
Topics





Introduction & Background
Problems facing OS development for
Reconfigurable systems
Changes to the usual development tools
Unresolved Issues
Conclusion
John Huisman
Operating Systems for Reconfigurable
Systems
2
Introduction

The main purpose of an OS is to increase the
abstraction between



The Application Designer
The System Software
An OS would help


Reduce knowledge of hardware
Increase the runtime flexibility of reconfigurable
programs
John Huisman
Operating Systems for Reconfigurable
Systems
3
Introduction cont…


An OS would also allow for better portability
of programs
Resent developments in FPGA technology
have allowed the exploration into an OS



Increases in the density of hardware
Selective reconfiguration of the hardware
Ability to support many dependent and
independent circuits
John Huisman
Operating Systems for Reconfigurable
Systems
4
Background

Few attempts to create a Reconfigurable
System Operating Systems

The Xputer system OS had an extension added to
communicate with reconfigurable hardware


It could only handle one user at a time and used
complete context switches
The SPACE.2 was also used to test an OS using
multiple reconfigurable chips


John Huisman
Used full context switching
Each user had it’s own dedicated chip
Operating Systems for Reconfigurable
Systems
5
The challenges in developing an OS for
reconfigurable systems

Reconfigurable systems emulate circuits and
this removes many elements from a
conventional OS



Lack of a defined program counter
No conventional retrieve, decode, execute cycle
Can have a varying amount of pipelines, making it
harder to know how to clear the system
John Huisman
Operating Systems for Reconfigurable
Systems
6
The challenges in developing an OS for
reconfigurable systems

In the Operating
systems discussed the
reconfigurable
hardware



Is connected between
the I/O devices and the
Memory
Is a slave to the CPU, the
CPU is the control of the
system
Makes the system very
flexible
John Huisman
Figure 1: Target Architecture
composed of a host CPU, a
reconfigurable device, and
external components
Operating Systems for Reconfigurable
Systems
7
The challenges in developing an OS for
reconfigurable systems

It should be noted that tasks that makeup the
programs that run on the operating systems
need to be set in a general format

Serves two purposes


Increase portability of the program
The OS becomes the interface between the task
and applying it on the hardware, regardless of the
hardware used
John Huisman
Operating Systems for Reconfigurable
Systems
8
Logic Frames



To simplify the circuit
outlook on the system
FPGA area is viewed
as a single block
The block is broken into
chips, then into logic
frames
This system works like
virtual memory
Figure 2: the FPGA Task Graph
John Huisman
Operating Systems for Reconfigurable
Systems
9
Scheduling

To schedule circuits and other parts of a
program each part is broken up into task



Each task is either placed on hardware or
computed on a CPU
A program is then composed of a task graph
By using tasks the program is already broken
down and makes it easier to for multiple
users
John Huisman
Operating Systems for Reconfigurable
Systems
10
Scheduling cont…



With scheduling for a normal OS tasks are
preempted for others all the time
In a reconfigurable system it would be much
harder know when to interrupt a task as the
execution is more ambiguous
One idea is to implement flags into the circuit
to tell the OS when the circuit can be taken
out
John Huisman
Operating Systems for Reconfigurable
Systems
11
Scheduling cont…


As reconfigurable hardware is used multiple
tasks can be run in parallel from multiple
users
To order tasks to execute many things can be
taken into consideration, notably



Priority of the program
Size of the task
Task level
John Huisman
Operating Systems for Reconfigurable
Systems
12
Scheduling cont…


Grouping can also be used in scheduling to
help reduce communication between circuit
swaps and resources needed in routing
The algorithm used needs to be




Small
Deterministic
Bounded
The above criteria needs to be true not only
for grouping but for many of the OS
operations
John Huisman
Operating Systems for Reconfigurable
Systems
13
Changes to the usual development tools

An OS needs to be able to start processing
tasks/programs as quickly as possible with as
little overhead as possible

To do this the development tools used to
allocate, place, and route circuits needs to be
changed to fit the requirements of an OS
John Huisman
Operating Systems for Reconfigurable
Systems
14
Allocation


Before a circuit can be placed, adequate
space needs to be found or made
Two approaches to this problem



Track space taken by circuits as they are placed
onto the reconfigurable hardware through an array
Scan the hardware for available space each time
a new circuit is to be placed onto the hardware
The first option is favorable as it would take
less time to look up then scan the hardware
John Huisman
Operating Systems for Reconfigurable
Systems
15
Allocation cont…

If there is not enough room for the circuit to
be placed onto the hardware the OS has two
options



Shelf the task to run later
Remove a current task and write in the task to be
placed onto the system
The scheduler can help avoid the first option
but if circuits are to be removed the OS must
decide what to remove
John Huisman
Operating Systems for Reconfigurable
Systems
16
Placement

Current design tools create efficient, high
quality solutions with no regard for time

For an OS, the placement algorithm
sacrifices the efficient use of space for speed

As density of hardware increase the tradeoff
of efficiency for speed can be justified
John Huisman
Operating Systems for Reconfigurable
Systems
17
Placement cont…


To decrease the time taken by the placement algorithm is to
simplify its execution
To do this two approaches to placement have been looked at


1-D resource placement model
2-D resource placement model
Figure 3: Reconfigurable resource models: (a) 1D area model; (b) 2D area model.
John Huisman
Operating Systems for Reconfigurable
Systems
18
Placement cont…

1-D placement




A fixed width for the reconfigurable area is used to
place a circuit, dividing the area into strips
Each circuit gets its own strip of area
Simplifies the placement algorithm by increasing
the constraints on the circuit
Increases the amount of unused space on the
reconfigurable hardware
John Huisman
Operating Systems for Reconfigurable
Systems
19
Placement cont…

2-D placement




Circuits are placed as close as possible into a
rectangle and placed onto the reconfigurable area
Rectangles are used as it is easy to track used
space and place new circuits
This is more complex then the 1-D model and
decreases the unusable area
Increases the amount of time needed for each
placement
John Huisman
Operating Systems for Reconfigurable
Systems
20
Placement Results
Figure 4: (a) 1D and 2D stuffing methods for different laxity classes, (b) Runtimes of the
reference and stuffing schedulers to schedule one task, depending on the laxity class.


As seen above the 2-D placement method outperforms the 1D placement in terms of tasks rejected
Time increase is linearly as placement detail increases
John Huisman
Operating Systems for Reconfigurable
Systems
21
Routing



Like placing, the routing method needs to be
quick and not as accurate as the current tools
As routing is NP-Hard it is hard to create a
quick algorithm that can consistently
generate good solutions
Two approaches to simplify routing


Use more area to increase the chance of success
Use predefined routing blocks provided to the OS
John Huisman
Operating Systems for Reconfigurable
Systems
22
Routing cont…



Largest problem with the system is the fact
that if routing a circuit fails new placements
and routing needs to be done
Each failure to route a circuit increases the
overhead of the OS
Both placement and routing methods need to
be reliable else the system would be plagued
by unpredictable overhead times
John Huisman
Operating Systems for Reconfigurable
Systems
23
OS Operation Time Results
Characteristic
Dimension
Figure 5: The total execution time for the complete process


Results from one of the papers outlining a new
reconfigurable OS
As the characteristic dimension decreases and/or
the number of tasks increase the time increases
John Huisman
Operating Systems for Reconfigurable
Systems
24
Unresolved issues in the area



No hard configuration standard for compiled
general tasks representing circuits, this means
OS for reconfigurable systems are only
academic
Most tests done on OS where done with small
dependent and independent circuits, can it
continue to operate when given large circuits
As of yet there are no meaningful benchmarks to
measure the effectiveness of a OS for
reconfigurable systems
John Huisman
Operating Systems for Reconfigurable
Systems
25
Conclusion



As discussed there have been forward steps
to the creation of an OS for reconfigurable
systems
As reconfigurable hardware technology
increases in density and complexity, an OS
will be needed
Advances the prospect of software/hardware
co-design
John Huisman
Operating Systems for Reconfigurable
Systems
26
References
1.
Steiger, C., Walder, H., Platzner, M., Operating Systems for
Reconfigurable Embedded Platforms: Online Scheduling of
Real-Time Tasks, IEEE Transactions on Computers, Vol 53,
No. 11, 2004, pg 1393-1407
2.
Wigley, G., Kearney, D., The Development of an Operating
System for Reconfigurable Computing, Proceedings. 20th
International Parallel and Distributed Processing Symposium,
2006, pg 1-8
3.
Wigley, G., Kearney, D., The First Real Operating System for
Reconfigurable Computers, Proceedings 6th Australasian
Computer Systems Architecture Conference, 2001, pg 130-137
John Huisman
Operating Systems for Reconfigurable
Systems
27
End
John Huisman
Operating Systems for Reconfigurable
Systems
28
Current Project Progress


Project is to create a co-processor to
speedup the operation of the Scatter Search
Algorithm
Working on the 0-1 knapsack problem as
described by “Scatter Search, methodology
and implementations in C” by Manuel Langna
and Rafael Marti
John Huisman
Operating Systems for Reconfigurable
Systems
29
Current Project Progress




Currently working on the implementation of
the scatter search algorithm for the
MicroBlaze soft-core created by Xilinx
Using the Sparta 3E starter board as the host
unit the MicroBlaze is applied
Profile the Scatter Search algorithm to find
bottlenecks
Create a co-processor based on the known
bottlenecks in the system
John Huisman
Operating Systems for Reconfigurable
Systems
30