Paul Rosinger

Bashir Al-Hashimi

Krishnendu Chakrabarty

Rapid generation of thermal-safe test schedules

Overheating has been acknowledged as a major issue in testing complex SOCs. Several power constrained system-level DFT solutions (power constrained test scheduling) have recently been proposed to tackle this problem. However, as it will be shown in this paper, imposing a chip-level maximum power constraint doesn't necessarily avoid local overheating due to the non-uniform distribution of power across the chip. This paper proposes a new approach for dealing with overheating during test, by embedding thermal awareness into test scheduling. The proposed approach facilitates rapid generation of thermal-safer test schedules without requiring time-consuming thermal simulations. This is achieved by employing a lowcomplexity test session thermal model used to guide the test schedule generation algorithm. This approach reduces the chances of a design re-spin due to potential overheating during test.

Introduction

Considering power consumption during test is important because recent industrial experience has shown that scan testing in some designs may consume almost 30X of peak power over its normal operation mode [START_REF] Shi | How power aware test improves reliability and yield[END_REF]. A difference of such a magnitude can easily lead to permanent damage to the device under test due to overheating, or, lead to reliability failures due to electro-migration.

Recent research has addressed the problems associated with the excessive power dissipation during test both at core and at system level. Core level solutions include improved ATPG algorithms [START_REF] Wang | ATPG for heat dissipation minimization during test application[END_REF], pattern ordering methods [START_REF] Flores | Assignment and reordering of incompletely specified pattern sequences targeting minimum power dissipation[END_REF], and scan chain and clocking scheme modifications [START_REF] Rosinger | Scan architecture with mutually exclusive scan segment activation for shift and capture power reduction[END_REF]. Existing system level solutions consist of various power-constrained test scheduling algorithms [START_REF] Chou | Scheduling tests for VLSI systems under power constraints[END_REF][START_REF] Muresan | A comparison of classical scheduling approaches in power-constrained block-test scheduling[END_REF][START_REF] Nicolici | Power conscious test synthesis and scheduling for BIST RTL data paths[END_REF][START_REF] Larsson | An integrated system-on-achip test framework[END_REF][START_REF] Iyengar | Precedence-based, preemptive, and power-constrained test scheduling for system-on-a-chip[END_REF][START_REF] Chakrabarty | Design of system-on-a-chip test access architectures under place-and-route and power constraints[END_REF][START_REF] Ravikumar | Simultaneous module selection and scheduling for powerconstrained testing of core based systems[END_REF][START_REF] Nourani | Power-time trade off in test scheduling for SoCs[END_REF] which limit the concurrency of the core tests based on a chip-level maximum allowable power limit. This paper focuses on system level tackling of overheating during test.

Figure 1. Effect of power density variations on

Silicon die hot spots resulted from localised heating occur much faster than chip-wide overheating due to the non-uniform spatial on-die power distribution. Accepting the assumption of non-uniform spatial power distribution, we belive that constraining the maximum chip-level power dissipation is not effective in avoiding localised overheating. To demonstrate this, we provide the following motivational example based on a hypothetical system shown in Figure 1. This system is a typical example of non-uniform power distribution: cores with different sizes dissipate the same amount of power. In a power constrained test scheduling scenario, for a power constraint of 45W the two test sessions TS1 = {C2,C3,C4} and TS2 = {C5,C6,C7} would be both accepted by the test scheduling algorithm. However, thermal simulation results show a large discrepancy in terms of maximum temperature between the two test sessions, 125.5°C for TS1 vs. 67.5°C for TS2. This difference is mainly because the power density (power per unit of area) varies significantly from one core to another. For example, the power density of core C2 is 4 times higher than that of C5.

This means that in order to efficiently avoid hot spots without unnecessarily reducing test concurrency, the spatial and temporal non-uniform thermal behaviour of the chip under test must be addressed directly, i.e. by validating the generated test schedules through thermal simulations. This paper proposes a new approach for dealing with overheating during test, by embedding thermal awareness into test scheduling. To the best of our knowledge, this is the first investigation where test session thermal models are employed to guide the test schedule, rather than chip-level power constraints [START_REF] Chou | Scheduling tests for VLSI systems under power constraints[END_REF][START_REF] Muresan | A comparison of classical scheduling approaches in power-constrained block-test scheduling[END_REF][START_REF] Nicolici | Power conscious test synthesis and scheduling for BIST RTL data paths[END_REF][START_REF] Larsson | An integrated system-on-achip test framework[END_REF][START_REF] Iyengar | Precedence-based, preemptive, and power-constrained test scheduling for system-on-a-chip[END_REF][START_REF] Chakrabarty | Design of system-on-a-chip test access architectures under place-and-route and power constraints[END_REF][START_REF] Ravikumar | Simultaneous module selection and scheduling for powerconstrained testing of core based systems[END_REF][START_REF] Nourani | Power-time trade off in test scheduling for SoCs[END_REF].

Proposed Test Session Thermal Model

Accurate thermal simulation can be very time consuming for complex chips, therefore it is essential to keep the number of test schedule re-generation due to thermal violations to a minimum. In order to achieve this, we propose a low-complexity test session thermal model used to guide the test schedule generation. This reduces the amount of accurate thermal simulations necessary for obtaining a thermal-safe test schedule.

The heat generated during a test session by an active core can be transfered away from the core through its lateral neighbourhood and through the heat spreader placed above the silicon die. Limited lateral heat spreading elevates the core temperature as the only available heat release path remains the vertical one, i.e. through the heat spreader. The basic idea behind the proposed thermal-aware test schedule generation approach is to maximise the amount of heat which can be dissipated through the lateral neighbourhood of each active core in a test session. The proposed test session thermal model captures at core granularity level the main heat transfer paths originating at the cores tested in a given test session. This model is inspired from the RC-equivalent architecture-level thermal model proposed in [START_REF] Skadron | Temperatureaware microarchitecture[END_REF] which exploits the duality between the thermal and electric domains by modelling an IC as a network of thermal resistances and thermal capacitances. In the RC thermal model, each core is represented as a node in the RC network and thermal adjacency is modelled with thermal RC pairs connecting the corresponding nodes.

To adapt the generic RC-equivalent model proposed in [START_REF] Skadron | Temperatureaware microarchitecture[END_REF] to the specific needs of the thermal-aware test schedule generation, we have made the following modifications:

1. Only steady-state temperatures are considered as they represent upper bounds for the transient thermal profiles of individual cores. Therefore, only the thermal resistances of the generic RC model are used.

2. The heat transfer between two cores tested concurrently is considered to be negligible, and hence the thermal resistances between cores tested in the same test session are removed. This is a valid assumption because, the amount of heat exchanged by two adjacent objects depends on their temperature difference, and the temperature difference between two active cores is less than that between an active and passive core.

3. The cores which are passive in the test session under consideration, are assumed to be thermally grounded, i.e. their temperature is equal to the ambient temperature and fixed for the entire duration of the test session.

These modifications of the thermal model simplify the thermal-aware test schedule generation while still producing effective solutions, as demonstrated by the experimental results reported in Section 4.

The following example illustrates the proposed test session thermal model. For the layout configuration shown in Figure 2, we assume the test session under consideration consists of the tests for cores 2,4 and 5. The white arrows show the lateral paths available for moving the heat away from the active cores. Figure 3 shows the thermal resistive model (modification 1) corresponding to this test session. The thermal resistances between the nodes corresponding to active cores are omitted (modification 2), while all remaining thermal resistances connect the active core nodes to the thermal ground (modification 3). The equivalent test session thermal model shown in Figure 4 will be used to guide the thermal-aware test schedule generation as follows. A small equivalent thermal resistance associated with an active core means good heat exchange between the core and the ambient, which predicts a low core temperature during test. On the other hand, a large equivalent thermal resistance associated with an active core means poor heat exchange with the ambient, and therefore signals a potential hot spot during test. Power dissipation differs from core to core, therefore, we are introducing the core thermal characteristic(TC) with respect to a given test session TS defined as: T C T S (i) = P (i) × R th (i), where P(i) is the average power dissipation for core i and R th (i) is the equivalent thermal resistance associated with core i with respect to TS. TC provides a normalised means for selecting the appropriate core to be added to a test session. This means that a core with a poor heat exchange configuration (large R th ) but low power dissipation has comparable chances to be assigned to a test session with a core which would exhibit good heat exchange with the ambient but has higher power dissipation.

The proposed thermal-aware test scheduling algorithm, which will be detailed in the next section, is driven by the test session thermal characteristic (STC), defined as follows:

STC(TS) = max C i ∈T S (T C T S (i) × P (i) × W (i)),
where W(i) is a weight associated with core i, and initially set to 1.

Thermal aware test schedule generation

The pseudocode for the proposed thermal-safe test schedule generation flow is given in Algorithm 1. The inputs to the algorithm are the set of cores(S) of the targeted system, the maximum allowable temperature(TL) and the maximum test session thermal characteristic limit (STCL). In the first stage (lines 1-7), the algorithm verifies if the temperature constraint is not violated by individual cores. For this, a purely sequential test schedule, i.e. only one core per test session, is simulated. If a thermal violation occurs, then it is either fixed by redesigning the test infrastructure of the core, or the temperature limit (TL) is increased. Once all individual temperature violations have been eliminated, the algorithm proceeds to the actual test schedule generation. New cores are added to an empty test session TS until STC(TS) exceeds the user-specified STCL(lines 9-15). Once no more cores can be added to TS, TS is simulated and the maximum temperature for each core in TS is compared with TL (line 19). If any thermal violation is detected at this stage, TS is discarded and the weight W of all cores which violated TL is increased. This is done in order to make them less likely to be added to a "busy" test session. If no thermal violation was detected, TS is added to the test schedule. The algorithm continues with a new session (line 9) until all cores have been scheduled.

Experimental results

In order to validate the efficiency of the proposed thermal-aware test scheduling approach, we have performed a set of experiments based on the Compaq Alpha 21368 floorplan from [START_REF] Skadron | Temperatureaware microarchitecture[END_REF]. The floorplan consists of 15 individual cores describes in terms of their size and position within the floorplan. The test power dissipationvalues used for these cores were ranging from 1.5X to 8X their power dissipation during normal operation. The experiments focus on two categories of results: the length of the generated test session and the simulation effort. By simulation effort we mean the amount of test session time which needs to be simulated until a thermal-safe test schedule is reached. In our experiments we have used the HotSpot tool [START_REF] Skadron | Temperatureaware microarchitecture[END_REF] to Algorithm 1 Thermal-safe test schedule generation INPUT: S, the core set of the targeted system TL = max. allowable temperature STCL = session thermal characteristic limit OUTPUT: Thermal-safe schedule as a list of thermal-safe test sessions Figure 5 shows the effect of the session thermal characteristic limit (STCL) on the length of the generated test schedules and on the required simulation effort for TL={145°C, 155°C, 165°C}. As can be seen, relaxed (large) STCL values lead to short test schedule at the expense of a significant simulation effort.

1 FOR EACH C i ∈ S 2 simulate( C i ) 3 BCMT(i) = MaxTemp( C i ) 4 IF BCMT(i) ≥ TL 5 fix core-level thermal violation OR increase TL 6 ENDIF 7 END FOR 8 A = { C i |C i ∈ S } 9 TS = ∅ 10 FOR EACH C i ∈ A 11 TS1 = TS C i 12 IF STC(TS1) ≤ STCL 13 TS = TS1 14 END IF 15 END FOR 16 simulate( TS ) 17 ValidSession = TRUE 18 FOR EACH C i ∈ T S 19 IF MaxTemp( C i ) ≥ TL 20 W i = W i ×
For example, when TL=145°C, a STCL value of 100 leads to a 3 second test schedule, but required a cumulated 26 seconds of test session time to be simulated until a thermal-safe schedule could be identified. The high simulation effort required is due to a large number of thermal violations (line 19 in Algorithm 1) which lead to additional test session generation iterations. As the STCL becomes tighter (smaller value), we notice an increase in the length of the generated test schedules, however the simulation effort involved is much lower compared to the previously discussed case. for very tight constraints (STCL ≤ 30), the simulation effort involved equals the length of the generated test schedule, i.e. a thermal-safe test schedule was identified from the first attempt, hence no additional simulations due to thermal violations were required. Figure 5 also shows that as TL in increased, the test schedules get shorter as more test could be assigned to the same test session without violating the thermal constraint. Also the simulation effort decreases because thermal-safe schedules are easier to generate under a more relaxed thermal constraint. Table 1 reports a more extensive set of results for TL in the 145-185°C range. In addition to the test schedule length and simulation effort, the simulated maximum temperature for the entire test session is also reported. As it can be seen, the maximum temperature approaches TL especially for very short test schedules, as they make better use of the temperature allowance.

For example, when TL=150°C, the maximum temperature for a 7 second test schedule was almost 6°C below TL, while for a 4 second test session, the maximum temperature was less than 1°C below TL. These results also show that depending on the STCL, for the same TL, reductions up to 3.5X in test schedule length can be obtained. Another interesting thing to be noted is the fact that for high TL and low STCL, the simulated maximum temperature can be up to 35°C below TL. For example, for TL=185, and STCL=30, the maximum temperature corresponding to the 6 second test stays under 145°C . This shows that in these cases, the STCL constraint is much stronger than TL.

Conclusions

In this paper we have proposed an approach for test schedule generation guided by a test session thermal model. To the best of our knowledge this is the first investigation targeting the overheating during test based on a thermal model of the test session, rather than imposing a chip-level power constraint. We belive a thermal-aware test scheduling approach is more effective than power constrained test scheduling approached, because of the known low correlation between silicon temperature and power dissipation. As demonstrated by the experimental results, this approach generates thermal-safe schedules, given a maximum temperature limit, while keeping the necessary computational effort to a minimum. Moreover, the proposed approach allows exploration of more efficient solution at the expense of longer thermal simulation times through a user selectable parameter.

Figure 2 .

 2 Figure 2. Test session example

Figure 3 .

 3 Figure 3. Test session thermal model of example in Figure 2

Figure 4 .

 4 Figure 4. Equivalent test session thermal model

  28 IF A = ∅ GO TO LINE 9; END IF 29 DONE perform thermal simulations, however other IC thermal simulation tools could be used just as well.

Figure 5 .

 5 Figure 5. Test schedule length and simulation effort vs. the session thermal characteristic limit

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

The first two authors would like to acknowledge the Engineering and Physical Sciences Research Council (EPSRC) for funding this work under grant no. GR/S05557. The authors also wish to thank the anonymous reviewers for their suggestions which helped improve the quality of the paper.


O Ozturk
email: ozturk@cse.psu.edu

H Saputra
email: saputra@cse.psu.edu

M Kandemir
email: kandemir@cse.psu.edu

Access Pattern-Based Code Compression for Memory-Constrained Embedded Systems*

As compared to a large spectrum of performance optimizations, relatively little effort has been dedicated to optimize other aspects of embedded applications such as memory space requirements, power, real-time predictability, and reliability. In particular, many modern embedded systems operate under tight memory space constraints. One way of satisfying these constraints is to compress executable code and data as much as possible. While research on code compression have studied efficient hardware and software based code strategies, many of these techniques do not take application behavior into account, that is, the same compression/decompression strategy is used irrespective of the application being optimized. This paper presents a code compression strategy based on control flow graph (CFG) representation of the embedded program. The idea is to start with a memory image wherein all basic blocks are compressed, and decompress only the blocks that are predicted to be needed in the near future. When the current access to a basic block is over, our approach also decides the point at which the block could be compressed. We propose several compression and decompression strategies that try to reduce memory requirements without excessively increasing the original instruction cycle counts.

Introduction

Most embedded systems have tight bounds on memory space. As a consequence, the application designer needs to be careful in limiting the memory space demand of code and data. However, this is not a trivial task, especially for large-scale embedded applications with complex control structures and data access patterns. One potential solution to the memory space problem is to use data and code compression.

Prior research in code compression studied both static and dynamic compressions techniques, focusing in particular on efficient compression/decompression strategies [START_REF] Abali | Memory Expansion Technology (MXT): Software Support and Performance[END_REF][START_REF] Benini | Hardware-Assisted Data Compression for Energy Minimization in Systems with Embedded Processors[END_REF][START_REF] Benini | Selective Instruction Compression for Memory Energy Reduction in Embedded Systems[END_REF][START_REF] Cooper | Enhanced Code Compression for Embedded RISC Processors[END_REF][START_REF] Ernst | Code Compression[END_REF][START_REF] Lefurgy | Evaluation of a High-Performance Code Compression Method[END_REF][START_REF] Lekatsas | Code Compression for Low-Power Embedded System Design[END_REF][START_REF] Lekatsas | Code Compression as a Variable in Hardware/Software Codesign[END_REF]. One potential problem with most of these techniques is that the compression and decompression decisions are taken in an applicationinsensitive manner; that is, the same compression/decompression strategy is employed for all applications independent of their specific instruction access patterns.

In this paper, we propose a control flow graph (CFG) centric approach to reducing the memory space consumption of executable binaries. The main idea behind this approach is to keep basic blocks of the application in the compressed form as much as possible, without increasing the original execution cycle counts excessively. An important advantage of doing so is that the executable code occupies less memory space at a given time, and the saved space can be used by some other (concurrently executing) applications. [START_REF] Abali | Memory Expansion Technology (MXT): Software Support and Performance[END_REF] The proposed approach achieves this by tracking the basic block accesses (also called the instruction access pattern) at runtime, and by invoking compressions/decompressions based on the order in which the basic blocks are visited. On the one hand, we try to save as much memory space as possible. On the other hand, we do not want to degrade the performance of the application significantly by performing frequent compressions and decompressions, which could potentially occur in the critical path during execution. This paper makes the following major contributions:

• It proposes a basic block compression strategy called the k-edge algorithm that can be used for compressing basic blocks whose current executions are over. • It proposes a set of basic block pre-decompression strategies, wherein a basic block is decompressed before it is actually needed, in an attempt to reduce the potential performance penalty that could be imposed by the on-line decompression. The rest of this paper is organized as follows. Section 2 summarizes basic concepts regarding the control flow graph based code representation, and the assumptions we made about our execution environment. Sections 3 and 4 discuss the basic block compression and decompression strategies, respectively, proposed in this paper. Section 5 gives the details of our implementation. Section 6 discusses related work on code compression. Section 7 concludes the paper by summarizing our contributions.

Program Representation and Architecture

A control flow graph (CFG) is an abstract data structure used in compilers to represent a procedure/subprogram [START_REF] Muchnick | Advanced Compiler Design and Implementation[END_REF]. Each node in the CFG represents a basic block, i.e., a straight-line piece of code without any jumps or jump targets; jump targets start a block, and jumps end a block. In this graph, jumps in the control flow are represented by directed edges. There are two specially designated blocks: the entry block, through which control enters into the flow graph, and the exit block, through which all control flow leaves. The CFG is essential to several compiler optimizations based on global dataflow analysis such as def-use chaining and use-def chaining [START_REF] Muchnick | Advanced Compiler Design and Implementation[END_REF]. It should be emphasized that a CFG is a static (and conservative) representation of the program, and represents all the alternatives of control flow (i.e., all potential execution paths). As an example, both arms of an if-statement are represented in the CFG, while in a specific execution (with a particular input), only one of them could actually be taken. A cycle in the CFG may imply that there is a loop in the application code. Figure 1 depicts an example CFG fragment that contains two loops.

The approach proposed in this paper saves memory space by compressing basic blocks as much as possible without unduly degrading performance. We assume a software-controlled code memory either in the form of an external DRAM or in the form of an on-chip SRAM (e.g., a scratch-pad memory [START_REF] Panda | Memory Issues in Embedded Systems-On-Chip: Optimizations and Exploration[END_REF]). It must be emphasized that our main objective in this study is to reduce the memory space requirements of embedded applications. However, if there is another level of memory in front of the memory where our approach targets (i.e., a memory between the target memory and the CPU), the proposed approach also brings reductions in memory access latency (as we need to read less amount of data from the target memory) as well as in the energy consumed in bus/memory accesses. However, a detailed study of these issues is beyond the scope of this paper.

Another important issue is that, while in most of the cases discussed in this paper we do not put a restriction on the total memory space that could be used by the application being optimized, our approach needs only a slight modification to address this issue. Specifically, all that needs to be done is to check before each basic block decompression whether this decompression could result in exceeding the maximum allowable memory space consumption, and if so, compress one of the decompressed basic blocks that are in the uncompressed form. One could use LRU or a similar strategy to select the victim basic block when necessary.

Basic Block Compression

In this section, we discuss the k-edge algorithm in detail. This algorithm compresses a basic block that has been visited by the execution thread when the k th edge following its visit is traversed. It is to be noted that the k parameter can be used to tune the aggressiveness of compression. Consequently, the k-edge algorithm actually specifies a family of algorithms (e.g., 1-edge, 2-edge, 10edge, etc). For example, let us consider the CFG illustrated in Figure 1. Assuming that we have visited basic block B 1 and, following this, the execution has traversed the edges marked as a and b, the 2-edge algorithm (i.e., the k-edge algorithm with k=2) starts Selecting a suitable value for the k parameter is important as it determines the tradeoff between memory space saving and performance overhead. Specifically, if we use a very small k value, we aggressively compress basic blocks but this may incur a large performance penalty for the blocks with high temporal reuse (though it is beneficial from a memory space viewpoint). In other words, if a basic block is revisited within a short period of time, a small k value could entail frequent compressions and decompressions (note that a basic block can be executed only when it is not in the compressed form). On the other hand, a very large k value delays the compression, which may be preferable from the performance angle (as it increases the chances of finding a basic block in the uncompressed form during execution when it is reached). But, it also increases the memory space consumption.

B 0 B 0 B 1 B 1 B 2 B 2 B 3 B 3 B 5 B 5
Another important issue is how one can perform compressions. Note that, in a single-threaded execution, the compression comes in the critical path of execution, and can slow down the overall execution dramatically. Therefore, we propose a multi-threaded approach, wherein there exists a compression thread (in addition to the main execution thread), whose sole job is to compress basic blocks at the background, thereby incurring minimal impact on performance. Specifically, the compression thread utilizes the idle cycles of the execution thread to perform compressions.

Basic Block Decompression

We have at least two options for performing basic block decompressions. In the first option, called the ondemand decompression (also called the lazy decompression), a basic block is decompressed only when the execution thread reaches it. That is, basic block decompressions are performed on a need basis. The most important advantage of this strategy is that it is easy to implement since we do not need an extra thread to implement it. All we need is a bit per basic block to keep track of whether the block accessed is currently in the compressed form or not. Its main drawback is that the decompressions can occur in the critical path, and thus degrade performance significantly. In the second option, referred to as the pre-decompression, a basic block is decompressed before it is actually accessed. The rationale behind this approach is to eliminate (or, at least reduce) the potential delay that would be incurred as a result of decompression. In other words, by pre-decompressing a basic block, we are increasing the chances that the execution thread finds the block in the uncompressed form, thereby not losing any extra execution cycles for decompressing it. This pre-decompression based scheme has, however, two main problems. First, we need a decompression thread to implement it. Second, predecompressing a basic block ahead of time can increase the memory space consumption.

It is easy to see that a pre-decompression based scheme can be implemented in different ways. In this paper, we study this issue by focusing on two different dimensions. First, we have a choice in selecting the basic block(s) to pre-decompress. Second, we have a choice in selecting the time to pre-decompress them. 2 These two choices obviously bring associated performance/memory space tradeoffs. For example, pre-decompressing more basic blocks increases the chances that the next block to be visited will be in the uncompressed form (which is preferable from the performance viewpoint provided that we are able to hide the decompression cost); but, it also increases the memory space consumption. Similarly, predecompressing basic blocks early (as compared to predecompressing them at the last moment) involves a similar tradeoff between performance and memory space consumption.

In this paper, we explore this two-dimensional predecompression search space using two techniques. First, to determine the point at which we initiate decompression, we use an algorithm similar to k-edge. In this algorithm (also called k-edge), a basic block is decompressed (if it is not already in the uncompressed form) when there are at most k edges that need to be traversed before it could be reached. As before, k is a parameter whose value can be tuned for the desired memory space -performance overhead tradeoff. An example is depicted in Figure 2. Assuming k=3, in this figure, basic block B 7 is decompressed at the end of basic 2 At this point, the analogyy between pre-decompression and softwareinitiated data/code pre-fetching should be noted. The two choices mentioned in the text correspond to selecting the blocks to prefetch and timing of prefetch in the context of prefetching. ). This is because, from the end of B 1 to the beginning of B 7 , there are at most 3 edges that need to be traversed. Second, to determine the basic block(s) to decompress, we use a prediction-based strategy. The idea is to determine the basic block that could be accessed next and to pre-decompress it ahead of the time. In this paper, we discuss two different prediction-based strategies. In the first strategy, called pre-decompress-all, we predecompress all basic blocks that are at most k edges away from the exit of the currently processed block. In the second strategy, called pre-decompress-single, we select only one basic block among all blocks that are at most k edges ahead of the currently processed basic block. It is to be noted that while pre-decompress-all favors performance over memory space consumption, predecompress-single favors memory space consumption over performance. To demonstrate the difference between these two pre-decompression based strategies, we consider the CFG fragment in Figure 2 again, assuming this time, for illustration purposes, that blocks B 4 , B 5 , B 8 , and B 9 are currently in the compressed form, all other blocks are in the uncompressed form, and the execution thread has just left basic block B 0 . Assuming further that k=2, in the pre-decompress-all strategy, the decompression thread decompresses B 4 , B 5 , B 8 , and B 9 . In contrast, in the pre-decompress-single strategy, we predict the block (among these four) that is to be the most likely one to be reached than the others, and decompress only that block. Figure 3 shows the decompression design space explored in this paper. Figure 4 summarizes our approach to code compression for reducing memory space consumption. It is assumed that the highlighted path is the one that is currently taken by the execution thread. In the ideal case, the decompression thread traverses the path before the execution thread and decompresses the basic blocks on it so that the execution thread finds them directly in the executable state. The compression thread, on the other hand, follows the execution thread and compresses back the basic blocks whose executions are over. The k parameters control the distance between the threads.

Implementation Details

In implementing the compression/decompressionbased strategy described, there is an important challenge that needs to be addressed. Specifically, when a basic block is compressed or decompressed, the branch instructions that target that block must be updated. In addition, the saved memory space (as a result of compressions) should be made available to the use of other applications with minimum overhead. In particular, one may not want to create too much memory fragmentation. This is because an excessively fragmented free space either cannot be used for allocating large objects or requires memory compaction to do so. Therefore, our current implementation slightly deviates from the discussion so far, in particular when compressions are concerned. Specifically, we start with a memory image, wherein all basic blocks are stored in their compressed form. Note that this is the minimum memory that is required to store the application code. As the execution progresses, we decompress basic blocks (depending on the instruction access pattern and the decompression strategy adopted, as discussed earlier), and store the decompressed (versions of the) blocks in a separate location (and keep the compressed versions as they are). Later, when we want to compress the block, all we need to do is to delete the decompressed version. In this way, the compression process does not take too much time. In addition, the memory space is not fragmented too much as the locations of the compressed blocks do not change during execution. We illustrate the idea using the example in Figure 5 with on-demand decompression. The figure shows an example CFG fragment, and traces the sequence of events for a particular execution scenario. Initially, all the basic blocks are in the compressed form and stored in the compressed code area. The program counter (PC) points to the entry of the first basic block, which is B 0 in this case [START_REF] Abali | Memory Expansion Technology (MXT): Software Support and Performance[END_REF]. Fetching an instruction from the compressed code area triggers a memory protection exception.

The exception handler decompresses block B 0 into B 0 ' and sets PC to the entry of B 0 ' [START_REF]An Introduction to Thumb[END_REF]. Assuming that block B 1 is the one that follows B 0 , after the execution of block B 0 , the PC points to the entry of block B 1 [START_REF] Benini | Hardware-Assisted Data Compression for Energy Minimization in Systems with Embedded Processors[END_REF]. Since B 1 is in the compressed code area, the exception handler is invoked to decompress B 1 into B 1 ' and update the target address of the branch instruction in B 0 and set the PC to the entry of B 1 ' (4). Let us now assume that the execution thread next visits B 0 again. Consequently, after the execution of B 1 ', we branch to the entry of B 0 [START_REF] Cooper | Enhanced Code Compression for Embedded RISC Processors[END_REF]. At this time, we do not need to decompress B 0 once again. The exception handler updates the target address of the last branch instruction of block B 1 ' to the entry of B 0 ', and subsequently sets PC to the entry of B 0 ' [START_REF] Debray | Cold Code Decompression at Runtime[END_REF]. Following B 0 ', the execution thread can branch to B 1 ' directly without generating any exception [START_REF] Ernst | Code Compression[END_REF]. Let us assume now that the execution next visits B 3 . Consequently, the PC points to the entry of this basic block [START_REF] Franz | Slim Binaries[END_REF]. Assuming that our compression strategy uses k=2, at this point, we delete the decompressed version of B 0 (which is B 0 '), and decompress B 3 into B 3 ' as illustrated in [START_REF] Fraser | Analyzing and Compressing Assembly Code[END_REF]. It is to be noted that, when we discard a decompressed block, we also need to update the target addresses of the branch instructions (if any) that jump to the discarded block. For this purpose, for each decompressed block, we also maintain a "remember set" that records the addresses of the branch instructions that jump to this block.

Another issue is how to keep track of the fact that k edges have been traversed so that we can delete the decompressed version of the blocks. Our current implementation works as follows. For each basic block, we maintain a counter, which is reset to zero when the basic block is executed. At each branch, the counter of each (uncompressed) basic block is increased by 1 and (the decompressed versions of) the basic blocks whose counter reaches k are deleted.

Discussion of Related Work

Many embedded systems rely on special hardware to execute compressed code, such as Thumb for ARM processors [START_REF]An Introduction to Thumb[END_REF], CodePack [START_REF] Kemp | A Decompression Core for PowerPC[END_REF] for PowerPC processors, and MIPS16 [START_REF] Kissel | MIPS16: High-Density MIPS for the Embedded Market[END_REF] for MIPS processors. However, the requirement for special hardware limits their general applicability. Lefurgy et al [START_REF] Lefurgy | Reducing Code Size with Run-Time Decompression[END_REF] propose a hybrid approach that decompresses the compressed code at the granularity individual cache lines. Kirovski et al [START_REF] Kirovski | Procedure-Based Program Compression[END_REF] present a procedure-based compression strategy that requires little or no hardware support. There has been a significant amount of work that explores the compressibility of program representations [START_REF] Hoogergrugge | A Code Compression System Based on Pipelined Interpreters[END_REF]. The resulting compressed form either must be decompressed (or compiled) before execution [START_REF] Ernst | Code Compression[END_REF][START_REF] Franz | Adaptive Compression for Syntax Trees and Iterative Dynamic Code Optimization: Two Basic Technologies for Mobile-Object Systems[END_REF][START_REF] Franz | Slim Binaries[END_REF], or it can be executed without decompression [START_REF] Cooper | Enhanced Code Compression for Embedded RISC Processors[END_REF][START_REF] Fraser | Analyzing and Compressing Assembly Code[END_REF]. A hybrid approach is to use an interpreter to execute the compressed code [START_REF] Fraser | Custom Instruction Set for Code Compression[END_REF][START_REF] Proebsting | Optimizing an ANSI C Interpreter with Superoperators[END_REF]. Compared to the direct execution approach, the interpreter-based approach usually allows more complex coding schemes, and thus, achieves smaller memory consumption for the compressed code. However, the interpreter itself occupies memory space.

Debray and Evans [START_REF] Debray | Cold Code Decompression at Runtime[END_REF] present a code compression strategy that operates at a function granularity, i.e., functions constitute compressible units. Their work exploits the property that for most programs, a large fraction of the code is rarely touched. Our work is different from theirs in at least two aspects. First, we operate on a finer granularity (basic block level). Therefore, we can potentially save more memory space (when, for example, a particular basic block chain within a large function is repeatedly executed, in which case our approach can keep the unused memory blocksin the functionin the compressed form). Second, we also employ pre-decompression that helps us reduce the negative impact of compression on performance.

Summary

This paper proposed a novel code compression strategy that is guided by the control flow graph (CFG) representation of an embedded program. In this strategy, the unit of compression/decompression is a single basic block of code. Conceptually, our approach employs three threads: one for compressing basic blocks, one for decompressing them, and one for executing the application code. We presented several predecompression techniques wherein a basic block is decompressed before it is actually needed, in an attempt to reduce the potential performance penalty caused by decompression

Figure 1 .

 1 Figure 1. An example CFG fragment. Assuming that the execution takes the left branch following B 0 , the 2-edge algorithm (i.e., the k-edge algorithm with k=2) starts compressing B 1 just before the execution enters basic block B 4

Figure 4 .

 4 Figure 4. The cooperation between the three threads during execution. The execution thread follows the decompression thread, and the compression thread follows the execution thread

[START_REF] Abali | Memory Expansion Technology (MXT): Software Support and Performance[END_REF] Alternately, in embedded systems that execute a single application, the memory space saved can enable the use of a smaller memory, thereby impacting both form factor and overall cost. As a third option, saved memory space can be used to increase energy savings in banked memory architectures. Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $

[START_REF] Muchnick | Advanced Compiler Design and Implementation[END_REF].00 IEEE

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

* This work was supported in part by NSF Career Award #0093082.

Compressed


Ryan Mannion
email: rmannion@cs.ucr.edu

Harry Hsieh

Susan Cotterell
email: susanc@cs.ucr.edu

Frank Vahid
email: vahid@cs.ucr.edu

System Synthesis for Networks of Programmable Blocks

The advent of sensor networks presents untapped opportunities for synthesis. We examine the problem of synthesis of behavioral specifications into networks of programmable sensor blocks. The particular behavioral specification we consider is an intuitive user-created network diagram of sensor blocks, each block having a pre-defined combinational or sequential behavior. We synthesize this specification to a new network that utilizes a minimum number of programmable blocks in place of the predefined blocks, thus reducing network size and hence network cost and power. We focus on the main task of this synthesis problem, namely partitioning pre-defined blocks onto a minimum number of programmable blocks, introducing the efficient but effective PareDown decomposition algorithm for the task. We describe the synthesis and simulation tools we developed. We provide results showing excellent network size reductions through such synthesis, and significant speedups of our algorithm over exhaustive search while obtaining near-optimal results for 15 real network designs as well as nearly 10,000 randomly generated designs.

Introduction

The availability of low cost, low power electronics has made ubiquitous monitoring and control realizable through the advent of sensor networks. Monitoring and controlling various aspects of a home, office, store, school, factory, or public spaces can result in improved personal comfort and safety, as well as public security. However, today's monitor/control systems are largely specialized, factory-programmed and configured to perform a specific application, such as home automation or intrusion detection. Though the applications of monitor/control systems are voluminous, high design cost has restricted all but the most commercially viable products from entering the market, resulting in an unfulfilled void of useful applications. For example, a homeowner may want notification of a garage door open at night or of a sleepwalking child; an office worker may want to know whether mail exists for him in the mailroom, a copy machine is free, or if conference rooms are in use. These applications are useful but lack the volume to justify producing dedicated products to address them, or results in high-priced dedicated products such that contracting a customized system would be cost prohibitive. A generalized set of building blocks that could be combined to perform a broad range of functions while maintaining ease of use would therefore serve a great need for non-programmer, nonengineer users to construct a variety of monitor/control systems.

Technological advances in miniaturization, wireless communication, and power efficiency have recently made feasible the development of low-cost, intelligent, and configurable networks of devices, known generally as sensor networks [START_REF] Akyildiz | Wireless sensor networks: a survey[END_REF] [START_REF] Hill | MICA: A Wireless Platform For Deeply Embedded Networks[END_REF][17] [START_REF] Warneke | Smart Dust: Communicating with a Cubic-Millimeter Computer[END_REF]. Returning to a previous example, instead of a dedicated garage open at night product, a user can connect a set of inexpensive reusable electronic blocks to build a system that accomplishes the same task. A garage open at night system would require a contact switch block, a light sensor block, a logic block, and an output block (e.g. buzzer or LED (light-emitting diode)) placed perhaps in a bedroom. A sleepwalk detector would utilize a motion sensor block, light sensor block, logic block and output block. A copy machine use detector might use just a motion sensor and output block. A conference room in-use detector might use motion and sound sensor blocks, logic blocks, and output blocks. Notice that the same blocks are usable in a variety of applications, enabling mass production and hence commercially viable low-cost blocks.

While many types of sensor networks utilize general-purpose programmable blocks [11][19], others have proposed using blocks with pre-defined functions and communication protocol [START_REF] Cotterrell | First Results with eBlocks: Embedded Systems Building Blocks[END_REF][13] [START_REF]Logiblocs[END_REF][16] [START_REF] Wyeth | Using Developmental Theories to Inform the Design of Technology for Children. Small Users -Big Ideas[END_REF]. Such pre-defined blocks enable unskilled people (in this case, people with no programming or hardware experience) to still build basic but useful systems, and may even reduce design time for skilled designers. However, while predefined blocks have ease of use advantages, they may result in more blocks in a network, resulting in larger network size, higher cost, and increased power consumption.

Therefore, we have developed capture, simulation and synthesis tools that enable a user to specify a network using predefined blocks (representing a behavioral description) and to simulate that network to verify correct behavior, and that automatically synthesize an optimized network using programmable blocks with automatically generated software.

We found a challenging part of the development of these tools to be the design of the algorithm for partitioning the behavioral description onto a minimum set of programmable blocks. Although we originally assumed the partitioning problem would be equivalent to standard partitioning problems or to existing technology mapping problems, we found that particular differences made impossible the use of existing algorithmshence, we developed a new decomposition algorithm to solve the problem.

In the following section, we discuss background work, and provide justification for our work in this area. In Section 3, we discuss the specification, the simulator, and the code generation aspect of the system synthesis. Section 4 focuses on the partitioning aspect of the synthesis process and introduces our algorithm for partitioning. Section 5 provides the experimental results on real designs, as well as on large randomly generated designs. We conclude in Section 6.

Background

Much of the previous work in sensor networks relates to development of general-purpose sensor nodes [START_REF] Hill | MICA: A Wireless Platform For Deeply Embedded Networks[END_REF] [START_REF] Warneke | Smart Dust: Communicating with a Cubic-Millimeter Computer[END_REF]. Synthesis related works focus largely on analysis or exploration [START_REF] Adlakha | Density, Accuracy, Latency and Lifetime Tradeoffs in Wireless Sensor Networks -A Multidimensional Design Perspective[END_REF][10] [START_REF] Tilak | Infrastructure Tradeoffs for Sensor Networks[END_REF][21] of communication issues for networks having large numbers (thousands) of irregularly structured networked wireless nodes.

Our focus is instead on smaller-scale networks whose nodes have particular functions and whose connectivity explicitly carries out a particular task [START_REF] Cotterrell | First Results with eBlocks: Embedded Systems Building Blocks[END_REF][13] [START_REF]Logiblocs[END_REF][16] [START_REF] Wyeth | Using Developmental Theories to Inform the Design of Technology for Children. Small Users -Big Ideas[END_REF], such as a garage open at night detector. In particular, we focus on eBlocks [START_REF] Cotterrell | First Results with eBlocks: Embedded Systems Building Blocks[END_REF] [START_REF] Cotterell | Applications and Experiments with eBlocks --Electronic Blocks for Basic Sensor-Based Systems[END_REF]. eBlocks feature four classes of "blocks," categorized by function, communicating with a standard protocol. Sensor blocks detect environmental stimuli, such as motion or the press of a button. Output blocks interact with the environment, such as emitting a beep or turning on an appliance via an electric relay. Though blocks normally connect directly to each other using wires, communication blocks allow for wireless communication or other methods (such as X10 [START_REF]X10 Protocol[END_REF]). Compute blocks perform a (typically pre-defined) function on inputs and generate output. A special type of compute block is a programmable block, which features a finite number of inputs and outputs and which can be programmed to implement custom functionality (including functionality of multiple pre-defined blocks). Pre-defined compute functions include combinational functions, such as a two or three input truth table, AND, OR, and NOT, and basic sequential functions, like a toggle, trip, pulse generate, and delay. Figure 1 shows a garage open at night eBlock system built from physical eBlocks.

We developed a simulator for all four classes of eBlocks and their behavioral interaction. The synthesis procedure, including that of design partitioning, can then reduce the total number of eBlocks by combining the predefined compute blocks into a smaller number of programmable compute blocks.

Design partitioning is a critical aspect for successful system level synthesis. During partitioning, we seek to replace clusters of eBlocks with programmable eBlocks and minimize the total number of eBlocks. This partitioning problem cannot be solved using approaches developed for the classic bin-packing problem or the knapsack problem, as we must mind at least two constraints when "packing" a programmable block: the number of inputs used and the number of outputs used. Solutions to the twodimensional bin-packing problem, commonly manifested in the cutting stock problem [START_REF] Alvarez-Valdes | A Computational Study of Heuristic Algorithms for Two-Dimensional Cutting Stock Problems[END_REF], are also not applicable to our problem. The input and output constraints of the programmable blocks are mutually independent, the number of inputs used in a programmable block has no effect on the number of outputs available, and vice versa, and thus our problem cannot be restated as a cutting stock problem.

Our partitioning problem is similar to the problem of synthesizing behavioral specifications to FPGAs (Field Programmable Gate Arrays). Specifically, our problem is closest to that of DAG (Directed Acyclic Graph) covering. DAG covering, as it relates to our problem, has been shown to be NPhard [START_REF] Keutzer | Computational complexity of logic synthesis and optimization[END_REF]. However, algorithms developed for finding solutions to DAG covering, particularly algorithms that map Boolean networks to LUTs (look-up tables), are not applicable to our problem for a number of reasons. First, we do not require that all nodes in our network graph be covered (i.e. not all blocks need to be replaced by a programmable block). In fact, circumstances in which a partition contains a single node are undesirable, as there is no net reduction in the size of the design with a one-to-one mapping of a pre-defined block to a programmable block. This relaxation of the problem increases the search space significantly as we must now consider partitions in which one or more nodes are not covered. Second, we define our optimal solution as a cover that covers the most number of blocks with the fewest number of partitions, analogous to the goal of minimum-area DAG covering. However, many DAG covering algorithms focus on finding minimum-delay solutions or approximations [START_REF] Chen | DAG-Map: Graph-based FPGA Technology Mapping for Delay Optimization[END_REF][5] [START_REF] Kukimoto | Delay-Optimal Technology Mapping by (DAG) Covering[END_REF]. Third, many existing DAG covering algorithms permit replication of nodes in each LUT/programmable block [START_REF] Francis | Chortle: A Technology Mapping Program for Lookup Table-Based Field Programmable Gate Arrays[END_REF], but duplicating code in the programmable blocks runs contrary to the need to minimize power usage in sensor networks.

Thus, we contend that a partitioning algorithm targeted to the problem of partitioning pre-defined compute blocks to a minimum number of programmable compute blocks with limited input/output solves a new and useful problem.

Design Framework

We have written a number of tools that enable the specification, simulation, partitioning, and code generation of eBlock systems. Figure 2 illustrates our tool chain.

Design Entry/Simulation

We developed a Java-based graphical user interface (GUI) and simulator for the design entry and simulation of an eBlock system, illustrated in Figure 3. A user can drag a block from a library of blocks, situated on the right edge of the simulator, to the workspace and connect the blocks together by drawing lines between circular representations of their input/outputs. The simulator incorporates eBlocks that sense or interact with their environment with an accompanying visual representation of their environmental stimuli/interaction (e.g. clicking on a light sensor will toggle a light bulb icon on and off).

The simulator contains behavioral representations of all available eBlocks. It also understands the underlying communication protocol and all the restrictions on the model of computation. The simulation is behaviorally correct and obeys general high-level timing, but no detailed timing characteristics can be inferred. Given that all communication between blocks is done serially using packets and hence globally asynchronous, and because the blocks deal with human-scale events rather than fast timing, such lack of timing detail is generally not a problem.

eBlock Partitioning

After completing a design in the simulator, the user can instruct the framework to minimize the number of computation eBlocks

Code Generation

Each partition generated by the partitioning tool utilizes the code generation tool. The tool assigns each block within a partition a level, defined as the maximum distance between the block and any sensor block (analogous to the primary input-based level definition in circuit partitioning). The code generation tool assigns levels by tracing the paths in the network, beginning with sensor blocks, and marking each block visited with an appropriate level. Blocks visited multiple times retain the greatest level value assigned to them. eBlock networks do not contain loops, so the levels for eBlocks in a network are well-defined.

The simulator maintains the behavior of each block, defined in a Java-like language that is automatically transformed to a syntax tree. The code generator attaches the syntax trees of every block in the partition so that the tool can evaluate trees in succession. Syntax trees are ordered in non-decreasing order and determined by the level of each block. The ordering of the syntax trees ensures that the tool does not evaluate a block's tree before any of its input blocks have produced output. As the tool merges each block's tree into the new programmable block's tree, the tool changes tree nodes that access a block's input or output into a variable access, where appropriate. Communication between two blocks in a partition will occur internally in a programmable block via variables. In the event that two or more blocks share variable names in their internal behavior code, the conflict is resolved through variable renaming.

The newly merged syntax tree specifies the behavior of the programmable block that will replace the partition. The simulator's interpreter evaluates the tree in the same manner as a non-programmable block. A user can select a programmable block and instruct the simulator to translate the syntax tree into C code for downloading and use in a physical block.

Since we have implemented physical programmable eBlock system prototypes, we were able to compile and download the generated code and use the output of the synthesis tool chain in real-world systems. The programmable eBlock prototype utilizes a Microchip PIC16F628 microcontroller (www.microchip.com) with 2 Kbytes of program memory and is available for under $2. Given that amount of program memory, the small size of each program describing a pre-defined block's function, and the scale of real eBlock systems, we make the practical assumption that a programmable block's program size constraint will not be violated by any partition. Making such violation even less likely is the fact that the block-partitioning problem is actually input/output limited, not size limited. However, even if a programmable block's memory size were exceeded, we could easily utilize a PIC with a larger memory, or extend our algorithm with size constraints.

Partitioning

As mentioned in Section 2, the general aim of the partitioning phase is to minimize the total number of blocks by replacing the greatest number of pre-defined compute blocks with fewer programmable blocks. Pre-defined compute blocks have identical internal components and thus have equal cost. A programmable compute block has slightly higher cost due to the programmability hardware, but less cost than two pre-defined compute blocks.

A more precise statement of the problem is as follows. We represent an eBlock system as a directed acyclic graph G = (V, E) where V is the set of nodes (blocks) in the graph and E is the set of edges (connections) between the nodes. We define sensor eBlocks as primary inputs, and output eBlocks as primary outputs. The objective of the partitioning phase is to find a set of subgraphs of non-primary input and non-primary output nodes (hereafter referred to as inner nodes) of G such that 1) each subgraph has at most i inputs and o outputs, where i and o correspond to the number of inputs and outputs available in a programmable block, 2) each subgraph must be replaceable by a programmable block that can provide equivalent functionality, and 3) the number of inner blocks after replacement is minimized. We assume a subgraph containing only a single node to be invalid, as it is undesirable to replace a pre-defined compute block with a programmable compute block due to slightly higher cost of the latter.

Exhaustive Search

Initially, we implemented an exhaustive search algorithm to see whether an exhaustive approach was reasonable with respect to computation time, and to provide optimum results for small problem instances. The search space consists of every combination of n blocks into n programmable blocks (a combination need not use every block). We utilized a simple pruning mechanism in which all "empty" programmable blocks in a combination are indistinguishable, and portions of the search tree removed accordingly. For example, if at a given point in the search tree we are able to assign a block to one of three empty programmable blocks, we only consider one such branch.

The run time of partitioning by exhaustive search naturally increased exponentially. With designs featuring fourteen inner blocks, the search did not conclude after four hours. Such run time of exhaustive search is not acceptable for designs with as few as eleven inner blocks, where a user must wait for about one minute. An exhaustive search is therefore overly prohibitive as eBlocks designs with eleven or more inner blocks are common, and thus a different approach is needed.

Decomposition Method -The "PareDown" Heuristic

We first implemented a heuristic that clusters nodes into subgraphs through aggregation. From a list of inner nodes connected to a primary input, the aggregation method repeatedly selects a node that fits within a programmable block as a partition. Though the aggregation method concludes quickly for cases in which the exhaustive search is impractical, the aggregation method is not capable of taking advantage of convergence and thus we found it often produced non-optimal results.

We sought to avoid the pitfalls of the aggregation method's lack of look-ahead capabilities, by utilizing a decomposition method heuristic we call PareDown, to detect convergence but not be constrained by a particular "depth" at which our heuristic looks ahead. Thus, the PareDown approach, shown in Figure 4, begins by selecting all internal blocks of a design as a candidate partition, and then removes blocks from the partition until input and output constraints are met, hence the moniker "decomposition method." If the algorithm finds a valid partition, the algorithm repeats on the remaining blocks and continues until no new partitions remain.

The choice of which block to remove from an invalid candidate partition is determined by computing a rank for all border blocks in the candidate partition and removing the block with the lowest rank. We define a border block as a block in which every output or every input connects to a block outside of the candidate partition. The block's rank is defined as the net increase or decrease in the combined indegree and outdegree of a candidate partition if that block is removed from the candidate partition. For blocks that have the same rank, removal priority is given to the following criteria, in order: 1) The block with the greatest indegree 2) The block with the greatest outdegree 3) The block with the highest level.

The decomposition method benefits from fast run times and produces results well beyond the practical range of the exhaustive search. A worst-case design would feature inner blocks that can fit into a partition by themselves but cannot form a valid partition when combined with any other block or blocks. A design of this form containing n inner blocks would therefore require n iterations through the algorithm's main loop. In the first iteration, the PareDown heuristic would check for a valid partition n times before eventually isolating a single block as a partition (an invalid result). Subsequent iterations check for valid partitions n-1 times and so forth. Accordingly, the total iterations through the decomposition method is n*(n+1)/2, or the sum of 1 to n. This total yields a time complexity of O(n 2 ).

Example

As an example, we will demonstrate the PareDown heuristic partitioning of an example eBlock design, the Podium Timer 3 design from [START_REF]eBlocks: Embedded System Building Blocks[END_REF]. The podium timer utilizes a set of eBlocks to build a system that can notify a person that his/her talk time is nearing the end, and that time has ended. The design consists of some buttons, output LEDs, and several internal pre-defined compute nodes, including combinational and sequential nodes.

We begin with the DAG representation of the design, shown in Figure 5(a). For ease of reference, we number each block. Figure 5(a) shows the initial selection by the PareDown heuristic of every interior block as a candidate partition, indicated by the shaded area, and the rank values for the border nodes 2, 8, and 9. We assume that the programmable block available features two inputs and two outputs.

Since the shaded partition in Figure 5(a) requires three outputs, the partition is invalid. The PareDown heuristic removes node 9, the node with the least rank value, as shown in Figure 5(b). The partition remains invalid and nodes 2 and 8 are considered for removal, being the border nodes (node 6 and 7 are not border nodes since one or more of their outputs connects to a block inside the candidate partition). The two border nodes have the same rank but node 8 has a greater indegree and is removed, as shown in Figure 5(c).

With a requirement of four outputs, the partition shown in Figure 5(c) is invalid. Subsequent steps remove nodes 7 and 6 from the partition, and the partition becomes valid, as indicated by the solid outline in Figure 5(d).

The algorithm is repeated on the remaining node(s): 6, 7, 8, and 9. The PareDown heuristic removes node 7 from the new candidate partition, and the new partition becomes valid. Again, the heuristic runs on the un-partitioned node(s), which consists only of node 7. Though the partition fits in a programmable block, the partition is invalid for containing only a single block. The heuristic halts, returning the result visualized in Figure 5(e).

Thus, the heuristic reduces the internal compute nodes from the initial user-defined 8 nodes to only 3 programmable nodes.

Experiments

Setup

We executed the decomposition and exhaustive search algorithms on a variety of designs of varying depths (maximum block level) and size on a 2GHz AMD Athlon XP PC. The designs included 15 actual eBlock systems appearing at [START_REF]eBlocks: Embedded System Building Blocks[END_REF], designed independently of our work for purposes other than synthesis. Some of those systems were intentionally designed to be small by avoiding multiple identical sensors whenever possible to maximize user-comprehension of the systems, whereas eBlock systems can easily involve several dozen nodes. Thus, we also developed a randomized eBlock system generator able to generate eBlock networks of varying sizes. We implemented both exploration algorithms, exhaustive and PareDown, in Java within the framework provided by the eBlocks simulator, with the two implementations each representing less than 100 lines of code, including the code to extract experimental data. We assumed the existence of a programmable block having two inputs and two outputs.

Table 1 summarizes the data collected during the experiments for the library-based designs. The Inner Blocks (Original) column indicates the number of inner blocks corresponding to the design specified by the Design Name column. The Inner Blocks (Total) column indicates the number of inner blocks in a given design after partitioning by either the exhaustive search or PareDown heuristic algorithm. The Inner Blocks (Prog.) column specifies, of the number of inner blocks after partitioning listed in the Inner Blocks (Total) column, the number of programmable blocks in the partitioned design, which is essentially the number of partitions found. The Time column specifies the execution time for either of the algorithm utilized. The Block Overhead column indicates the number of additional inner blocks required after partitioning by the heuristic algorithm compared to optimal results of the exhaustive search algorithm. The % Overhead indicates the percent increase in the final design when the heuristic is utilized compared to the optimal results of the exhaustive search algorithm.

In addition to the library of designs used in our experiments, we ran the exhaustive search and heuristic algorithms on a sample of randomly generated designs. Table 2 shows the corresponding results. The random designs' inner block count varied between three and forty-five inner blocks as illustrated in the Inner Blocks (Original) column. The Number of Designs column specifies the number of designs considered for a given inner block counts.

Runtime Performance

The decomposition algorithm achieves significant speedup over the exhaustive search throughout the entire range of inner block values. Though exhaustive search maintains a reasonable runtime up to ten inner blocks, adding more inner blocks has a dire effect on the exhaustive search's computation time. Inner block sizes of thirteen or more yield unacceptable wait times for a user.

Beyond thirteen inner blocks, the decomposition method continues to process large designs in a reasonable amount of time and is therefore a good replacement for the exhaustive search. Though not displayed in Table 2, the decomposition method produced a result for a design with 465 inner nodes in 80 seconds. We note that it is highly unlikely that a real-world eBlocks design would feature 465 inner nodes. Thus, our method should be sufficiently fast for all practical eBlock designs.

Optimality

The decomposition method achieves excellent results that are optimal or within 15% of an optimal solution for every inner block size in which data was available from the exhaustive search. As indicated in Table 1 and Table 2, the solution generated by the decomposition method for the displayed range of inner block sizes is within one block of an optimal solution, on the average.

Conclusions and Further Work

We have demonstrated a working system for synthesizing behavioral models of eBlock networks into code and connectivity for physical eBlocks. We focused on the partitioning aspect of synthesis and introduced the PareDown heuristic. We have shown that PareDown is an effective method for rapidly finding optimal or near-optimal solutions to eBlock partitioning for both realworld designs and generated ones.

We plan to extend the PareDown heuristic to consider multiple types of programmable blocks (having different number of inputs and outputs) and varying compute block costs, and to

Figure 1 :

 1 Figure 1: Garage-open-at-night system built using eBlock prototypes.

Figure 2 :

 2 Figure 2: Design framework. Design Entry/ Simulation

Figure 3 :

 3 Figure 3: eBlock graphical capture and simulator tool.

Figure 4 :

 4 Figure 4: Decomposition method pseudocode.

Figure 5 :

 5 Figure 5: Decomposition method example.

Table 1 :

 1 Results for exhaustive search and PareDown decomposition using design library.

			Averages for Exhaustive Search		Averages for "PareDown" Decomposition
	Inner Blocks (Original)	Design Name	Inner Blocks (Total)	Inner Blocks (Prog.)	Time	Inner Blocks (Total)	Inner Blocks (Prog.)	Time	Block Overhead	% Overhead
	2	Ignition Illuminator	1	1	<1ms	1	1	<1ms	0	0 %
	2	Night Lamp Controller	1	1	<1ms	1	1	<1ms	0	0 %
	2	Entry Gate Detector	1	1	<1ms	1	1	<1ms	0	0 %
	2	Carpool Alert	1	1	<1ms	1	1	<1ms	0	0 %
	3	Cafeteria Food Alert	1	1	<1ms	1	1	<1ms	0	0 %
	3	Podium Timer 2	1	1	<1ms	1	1	<1ms	0	0 %
	3	Any Window Open Alarm	3	0	<1ms	3	0	<1ms	0	0 %
	3	Two Button Light	3	1	<1ms	3	1	<1ms	0	0 %
	5	Doorbell Extender 1	5	0	<1ms	5	0	<1ms	0	0 %
	6	Doorbell Extender 2	6	0	9ms	6	0	<1ms	0	0 %
	8	Podium Timer 3	3	3	125ms	3	2	<1ms	0	0 %
	10	Noise At Night Detector	6	4	4.79 s	6	4	<1ms	0	0 %
	19	Two-Zone Security	--	--	--	10	3	<1ms	--	--
	19	Motion on Property Alert	--	--	--	19	0	<1ms	--	--
	23	Timed Passage	--	--	--	14	5	<1ms	--	--
									--= no data available

Table 2 :

 2 Results for exhaustive search and PareDown decomposition using randomly generated designs.

			Averages for Exhaustive Search		Averages for "PareDown" Decomposition
	Inner Blocks (Original)	Number of Designs	Inner Blocks (Total)	Inner Blocks (Prog.)	Time	Inner Blocks (Total)	Inner Blocks (Prog.)	Time	Overhead Block	% Overhead
	3	1531	1.83	0.81	<1ms	1.87	0.79	<1ms	0.04	2 %
	4	982	2.24	1.22	<1ms	2.33	1.10	<1ms	0.09	4 %
	5	542	2.51	1.52	1.33ms	2.62	1.32	<1ms	0.11	4 %
	6	432	3.08	1.74	6.56ms	3.36	1.49	<1ms	0.28	9 %
	7	447	3.77	2.00	25.52ms	4.09	1.73	<1ms	0.32	8 %
	8	350	4.11	2.32	122.97ms	4.56	1.93	<1ms	0.45	11 %
	9	340	4.67	2.60	719.90ms	5.24	2.17	<1ms	0.57	12 %
	10	199	5.04	2.93	4.53s	5.76	2.45	<1ms	0.69	14 %
	11	170	5.47	3.20	31.77s	6.29	2.59	<1ms	0.82	15 %
	12	31	4.58	3.23	3.67min	4.87	2.58	<1ms	0.29	6 %
	13	6	6.84	3.17	29.93min	7.83	2.83	<1ms	0.99	14 %
	14	1311	--	--	--	8.11	3.05	<1ms	--	--
	15	1184	--	--	--	8.67	3.32	<1ms	--	--
	20	928	--	--	--	11.09	4.70	<1ms	--	--
	25	691	--	--	--	13.93	5.97	1.86ms	--	--
	35	354	--	--	--	19.63	8.26	4.82ms	--	--
	45	165	--	--	--	25.43	10.62	13.28ms	--	--
									--= no data available

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05) 1530-1591/05 $ 20.00 IEEE

Acknowledgements

This work was supported by the National Science Foundation (CCR-0311026) and by a Department of Education GAANN fellowship, and aided by donations from Microchip Technology Corporation.