Gang Chen

Hai Jin
email: hjin@hust.edu.cn

Deqing Zou

Weiqi Dai

On-demand Proactive Defense against Memory Vulnerabilities

Keywords:

Memory vulnerabilities have severely affect system security and availability. Although there are a number of solutions proposed to defense against memory vulnerabilities, most of existing solutions protect the entire life cycle of the application or survive attacks after detecting attacks. This paper presents OPSafe, a system that make applications safely survive memory vulnerabilities for a period of time from the starting or in runtime with users' demand. OPSafe can provide a hot-portable Green Zone of any size with users' demand, where all the subsequent allocated memory objects including stack objects and heap objects are reallocated and safely managed in a protected memory area. When users open the green zone, OPSafe uses a comprehensive memory management in the protected memory area to adaptively allocate buffers with multiple times of their defined sizes and randomly place them. Combined with objects free masking techniques, OPSafe can avoid overrunning each other and dangling pointer errors as well as double free or invalid free errors. Once closing the green zone, OPSafe clears away all objects in the protected area and then frees the protected area. We have developed a Linux prototype and evaluated it using four applications which contains a wide range of vulnerabilities. The experimental results show that OPSafe can conveniently create and destruct a hot-portable green zone where the vulnerable application can survive crashes and eliminate erroneous execution.

Introduction

Memory bugs severely affect system security and availability. Programs written in unsafe languages like C and C++ are particularly vulnerable because attackers can exploit memory errors to control vulnerable programs. These vulnerabilities can also cause programs failures. According to a survey conducted by IT industry analyst firms [START_REF]Vision Solutions Staff, Assessing the Financial Impact of Downtime[END_REF], the average business loss of an hour of IT system downtime is between US $84,000 and US $108,000. However, previous study showed that the average time to diagnose bugs and generate patches is 28 days. During this long time vulnerable window, users have to either stop running the program which cause the costly program downtime, or continuing running the program which experience problems such as potential crashes and attacks. Neither of the two behaviors is desirable. Therefore, it is significant to survive attacks to preserve system availability.

There are a number of solutions have been proposed to protect programs against memory vulnerabilities. One direction is for buffer overflow prevention, including return address defense on the stack [START_REF] Cowan | StackGuard: Automatic Adaptive Detection and Prevention of Buffer-overflow Attacks[END_REF][START_REF] Prasad | A Binary Rewriting Defense Against Stack Based Buffer Overflow Attacks[END_REF], array bounds checking, pointers protection via encrypting pointers, and address obfuscation via randomizing memory layout [START_REF] Bhatkar | Efficient Techniques for Comprehensive Protection from Memory Error Exploits[END_REF]. These approaches can improve the safety while drop the availability. The reason is that programs are always terminated when detecting attacks. The other direction is for heap-related bug prevention [START_REF] Berger | DieHard: Probabilistic Memory Safety for Unsafe Languages[END_REF][START_REF] Gao | First-Aid: Surviving and Preventing Memory Management Bugs During Production Runs[END_REF], which well balances the safety and availability of the applications. However, these techniques cannot be applied for protecting against stack buffer overflow attacks.

Previous solutions on protecting against memory vulnerabilities had to protect the entire life cycle of the application, or survive attacks after detecting attacks. However, users only need protection for a period of time at most times, especially for desktop applications. For example, when users use a browser to submit works, they need the browser not occurring any faults until the works have been submitted successfully.

In this paper, we propose a on-demand proactive protection system called OPSafe, which can make applications safely survive memory vulnerabilities for a period of time from the starting or in runtime with users' demand. When users need to protect the program against memory vulnerabilities, OPSafe can dynamically reallocate all the subsequent allocated memory objects in an protected memory area, called Green Zone, and it can also conveniently break away from the program to terminate the protection when users will not protect the program. In the green zone, OPSafe adopts the memory randomization technique in the protected memory area, which adaptively allocates buffers with multiple times of their defined sizes and places semantically infinite distance between memory objects to provide an probabilistic memory safety. This technique can greatly avoid overrunning between memory objects as well as dangling pointer errors. By omitting invalid free, OPSafe can mask double-free and invalid free errors. When closing green zone, OPSafe clears away the objects in the protected area and then frees the protected area. Our green zone is hot-portable with a feature of conveniently creating and destructing for running applications. As a result, OPSafe can provide a hot-portable green zone of any size for an application with users' demand.

To demonstrate the effectiveness of OPSafe, we have implemented a Linux prototype and evaluated it using four applications that contain a wide range of memory vulnerabilities including stack smashing, heap buffer overflow, doublefree and dangling pointer. Our experimental results show that OPSafe can protect applications against memory vulnerabilities in the green zone with a reasonable overhead.

In summary, we make the following contributions.

-We propose OPSafe, an on-demand proactive protection system to make applications safely survive memory bugs for a period of time from the starting or in runtime with users' demand. -We propose a concept, a hot-portable green zone of any size with users' demand, which can conveniently protect the applications at any times. It can protect the applications from the beginning or in runtime, and slice away from applications at any times, both decided by users. -We have implemented OPSafe on a Linux system, and evaluated its effectiveness and performance using four applications that contain a wide ranges of memory vulnerabilities.

The rest of the paper is organized as follows. The OPSafe overview, including the motivation, the background, the architecture, the workflow and important steps of OPSafe, are introduced in section 2. Section 3 describes the important implementation techniques. The experimental and analytical results are presented in section 4. Section 5 gives an overview of related work. Finally, we summarize our contributions in section 6.

OPSafe Overview

In this section, we first introduce our motivation, and then give an overview of the architecture and workflow of OPSafe.

Motivation

Memory vulnerabilities have severely affected system security and availability. Full life-cycle protection for an application is common most of times. However, sometimes we may need the application to be secure and reliable only for a period of time, especially for desktop applications. For example, when we write an important email via an email client, we need the client not crashed in the writing. However, we may not mind crashing in normal use because restarting the client is also convenient. Moreover, we even do not want to use the protection tool to protect the client in normal use because they affect the use of the client more or less from the performance or the function.

A great number of solutions on handling with memory vulnerabilities have been proposed, but they are designed from the view on how to respond to attacks without considering the users' demand. They can be classified into three categories: proactive full life-cycle protections which protect the application from the starting to the termination, fail-stop approaches which terminate the application for security when detecting a fault, and self-healing approaches which learn from the fault and automatically temporarily fix the bugs. All of these solutions should always monitor the application and not conveniently slice away from the application.

Take the email client as an example again. A user wants a green zone and also can conveniently control the size of the green zone for the email client.

The green zone can only be opened with the user demand. When writing the important email, the user can open the green zone. In this green zone, the user does not mind using more resource to make sure the security and availability of the application. When the resource occupied by the protection tool is needed to do other things, the user can conveniently close the green zone. Therefore, we need an on-demand proactive defense mechanism which can safely and effectively survive memory vulnerabilities in the green zone and have no effect outside of it for an application.

The memory management of OPSafe is based on our previous work SafeStack [START_REF] Chen | SafeStack: Automatically Patching Stack-based Buffer Overflow Bugs[END_REF] and Memshepherd [START_REF] Zou | Memshepherd: Comprehensive Memory Bug Fault-Tolerance System[END_REF]. SafeStack proposes the memory access virtualization mechanism to reallocate stack objects into a protected memory area. Memshepherd integrates the memory access virtualization mechanism into DieHard's design on the probabilistic safe heap memory allocator to reallocate heap objects into a safe heap space. In this heap space, memory objects are randomly placed in large chunks called miniheaps. However, Memshepherd should manage all the memory objects from the starting of the application, which can incur a high overhead and make the performance of the application degrade.

OPSafe Architecture

The architecture of OPSafe is illustrated in Figure 1a. OPSafe consists of several components, including a Stack Objects Information Extractor used to extract the information of stack buffers from the binaries, a Control Unit used to respond users' demand to generate a green zone (i.e., a protection window to protect and to end protection for the application), a Memory Allocator Extension used to reallocate all memory objects including stack objects and heap objects into the protected memory area, and a Memory Free Extension used to free the protected memory area.

Based on a dynamic instrumentation infrastructure, OPSafe can generate a hot-portable green zone for the application, including allocating and freeing memory objects. To reallocate the stack objects into the protected memory areas, OPSafe should get the location and size information of the original stack objects, which is gained by the static analysis from the Stack Objects Information Extractor.

Workflow of OPSafe

The workflow of OPSafe is illustrated in Figure 1b. Users can arbitrarily open or close the green zone on demand. The stack buffer information can be extracted from binaries before opening the green zone.

When users request to open the green zone, OPSafe creates a protected memory area and uses the Memory Allocator Extension to dynamically reallocate all the memory objects into the protected memory area with the dynamic instrumentation infrastructure. The memory allocation contains two parts. One is stack access redirection which is the basis of memory access virtualization. It is used to reallocate the stack objects into the protected memory area and redirect the memory access from the original address to the corresponding protected memory address. In this redirection, OPSafe should locate the original address of stack objects which can be gained from the buffer information. The other is heap reallocation which is used to intercept the heap allocation functions and replace them with our allocation functions to make all the heap objects be allocated in the protected memory area. In the protected memory area, OPSafe maintains stack objects of a function until the function exits and marks the the memory area of an heap object can be used when the application frees it.

When users request to close the green zone, OPSafe uses the Memory Free Extension to restore the memory management of the application and gradually frees all the memory objects in the protected memory area. OPSafe firstly removes all the reallocation instruments for stack objects and heap objects reallocation. In addition, OPSafe checks all miniheaps to free the unused miniheaps. If there are miniheaps in use, OPSafe then continues to monitor them. Once all the rest of miniheaps have been freed, OPSafe destructs the green zone by removing all the free operation instruments and gracefully slicing away from the application. After that, the green zone is closed.

OPSafe Implementation

In our implementation, our protected memory area is a heap space which is managed in the same way as Memshepherd. We should note that our protected memory area is not tied with Memshepherd's memory management, but also can be combined with other safe memory management mechanisms. In this section, we discuss the stack buffer information extraction, the green zone creation, maintenance and destruction.

Stack Buffer Information Extraction

The stack buffer information consists of the function level information and the variable level information. The function level information contains the function name, the starting code address and the number of stack buffer variables. The variable level information contains the variable name, size, offsets from the frame pointers for each local variables and parameters for buffers. As Memshepherd extracts stack buffer information according to the memory objects access pattern, the information is not accurate. However, if the program is compiled with debugging option (-g in GCC), the compiler adds debugging information about all variables in the program binaries. We extend Memshepherd's buffer information extractor with debugging information for the applications compiled with debugging option.

OPSafe uses TIED [START_REF] Avijit | TIED, LibsafePlus: Tools for Runtime Buffer Overflow Protection[END_REF] with an extension to extract debugging information for stack buffers. TIED cannot extract the stack buffer information from function main as the offset is relative to the stack pointer. OPSafe organizes all the buffer related information according to TIED, but makes some changes to the data structure of the buffer related information for future effective diagnoses, and also OPSafe does not need to rewrite the program binaries with the buffer related information as TIED does.

Green Zone Creation

When users request to open the green zone, OPSafe uses the dynamic instrumentation tool to intercept the memory allocation operations, including stack objects allocation and heap objects allocation. In addition, OPSafe creates the protected memory area which is allocated adaptively according to usage requirements.

For stack objects allocation, OPSafe only redirects the stack buffers in the subsequent called functions into the protected memory area. To redirect these stack buffers access, OPSafe should firstly locate the original addresses of stack buffers according to the stack buffer information, and then map the original addresses to the new corresponding addresses in the protected area. This is done when the register ESP becomes smaller. As the stack buffers have not been initiated at that time, OPSafe can benefit from avoiding copying data from the original memory addresses to the new corresponding addresses. For the stack buffers in the current stack, OPSafe maintains the original memory access to these stack buffers.

For heap objects allocation, OPSafe intercepts all the heap allocation functions in libc and replaces them with OPSafe's heap allocation functions, such as the function malloc. OPSafe only reallocates the subsequent heap objects requests after green zone creation, and the management for the previous allocated heap objects is still maintained by the application.

Green Zone Maintenance

After memory objects reallocation, OPSafe maintains the life cycle of these memory objects in the green zone. For the memory objects outside of the green zone, OPSafe leaves them into the management of the application.

For the stack buffers access, there are three types of access for them in the memory access virtualization, including direct access, indirect access and pointer access. The access mode is "Base plus Offset" for direct access and "Base plus Index plus Offset" for indirect access. The base is the base register, i.e., EBP or ESP, the offset is the offset is the value between the starting address of the array and the base register, and the index is the index register which stores the stack buffer index. For these two cases, OPSafe calculates the starting address of the stack buffer and replaces with the corresponding protected memory address. The pointer access means stack buffer is accessed by pointers, such as a stack buffer is passed an argument to a function. As there must be an instruction to get the address of the stack buffer, OPSafe can replace it without continuing to map the memory access from the pointer. When a function returns, OPSafe frees all the stack buffers of the function in the protected memory area.

For the heap object access, there are no extra memory mapping operations. When freeing a heap object, OPSafe checks whether it is in the green zone or not. If so, OPSafe then checks whether the heap object has been freed or the address of the heap object is invalid. For the double-free or invalid free, OPSafe can mask this error by omitting these memory free operations. If the heap object is outside of the protected memory area, OPSafe leaves the management of these objects and make the application to call the original libc function free to free it.

Green Zone Destruction

When users request to close the green zone, OPSafe enters into the green zone destruction phrase to gradually free all the memory objects in the green zone and restore the memory management of the application.

In this phrase, OPSafe firstly checks all the miniheaps in the green zone to determine which the miniheap can be freed. If there are miniheaps which are unused (i.e., do no store any memory objects), OPSafe frees these miniheaps. For the miniheaps which are in use, OPSafe should wait until all the memory objects of a miniheap have been freed. The memory objects in a miniheap consists of stack objects and heap objects. OPSafe frees stack objects of a function when the function returns and frees heap objects when the application call the libc function free to free them. In addition, OPSafe does not need to redirect the subsequent stack objects of new called functions and intercept the memory allocation operations of the application.

Finally, when all the miniheaps has been freed, OPSafe destructs the green zone by removing all the instrumentation for the application to restore the memory management of the application. After that, the application runs as original.

Experimental Evaluation

We have implemented a Linux prototype system with the operating system kernel Linux 2.6, and Pin 2.12-56759 is used as our dynamic instrumentation infrastructure. Our evaluation platform consists of two machines connected with 100Mbps Ethernet. One machine is configured with the Intel E5200 dual core 2.5GHz processors and 4GB memory. They are used to deploy OPSafe and our test suite. The other is configured with Intel E7400 dual core 2.8GHz processors and 4GB memory. It is used to run clients for testing servers and servers for testing desktop clients. We first describe the details of our test suite which are a range of multiprocess and multi-threaded applications. Then we present the results of the evaluation on the effectiveness of OPSafe under our test suite. To test the effectiveness, we use OPSafe to protect our test suite to survive memory vulnerabilities. Finally, we discuss the performance evaluation.

Overall Analysis

Our test suite contains four applications, including a ftp server ProFTPD, a web server Null-HTTPd, an email client Pine and a macro processor GNU M4, which are listed in Table 1. All these applications contain various types of bugs, including stack overflow, heap overflow, double free and dangling pointer. Four of the vulnerabilities are real-world vulnerabilities, and the double free bug is manually injected into the web server Null-HTTPd, named Null-HTTPd-df in Table 1.

Exploit CVE-2010-4221 in ProFTPD enables attackers corrupt memory to crash the ftp server or execute arbitrary code by sending data containing a large number of Telnet IAC commands to overrun stack buffers in the vulnerable function pr cmd read. OPSafe can avoid overrunning the control structures in the stack by moving the stack buffers of the vulnerable function into the protected memory area.

Exploit CVE-2002-1496 in Null-HTTPd is caused by improper handling of negative Content-Length values in HTTP header field. By sending a HTTP request with a negative value in the Content-Length header field, a remote attacker could overflow a heap buffer and cause the web server to crash or execute arbitrary code in the system. OPSafe can avoid attackers gain control by segregating all the heap metadata from the heap in the protected memory area. In addition, OPSafe can avoid the vulnerable heap objects overrunning other heap objects with high probability by multiple times of their defined sizes and a random placement strategy.

Exploit manually injected in Null-HTTPd-df is caused by a piece of injected vulnerable code. It frees a heap object which has already been freed. OPSafe can mask this double free error by intercepting the free operation, checking it and omitting invalid free operation.

Exploit CVE-2002-1320 in Pine enables attackers send a fully legal email message with a crafted From-header to force Pine to core dump on start-up. The only way to launch pine is manually removing the bad message either directly from the spool, or from another mail user agent. Until the message has been removed or edited there is no way of accessing the INBOX using Pine. The heap overflow is caused by the incorrect calculation of string length in the function est size, a message's header "From:" which contains a long string of escaped characters can cause a buffer used by the function addr list string to overflow. OPSafe can allocate an object with multiple times of defined size and a random placement strategy to avoid overrunning with high probability.

Exploit the dangling pointer in GNU M4 causes an misbehavior such as printing out misleading information when a macro whose arguments are being collected is redefined or deleted. Through deleting the definition from the symbol table, it can leave dangling pointers in the local variable sym of the function expand macro and then use dangling pointers leading M4 misbehavior. OPSafe can avoid this misbehavior as it does not really free a heap object in the green zone. It holds the content of the object and only marks the memory space be used. Fortunately, the random placement strategy of OPSafe can make it unlikely that a newly freed object will soon be overwritten by a subsequent allocation. Therefore, OPSafe can avoid this dangling pointer attacks with high probability.

Effectiveness Evaluation

We evaluate the capability of fault tolerance by comparing OPSafe with the restart method. We use a lightweight web server Null-HTTPd in this experiment. We adopte the apache benchmark ab to test the web server throughput and a network traffic and bandwidth usage tool nload to get a real time throughput with a 100ms interval. In addition, malicious requests are sent every 5s to crash the web server. All these two cases have adopted the restart method which restarts the web server when it crashes, and the results are shown in Figure 2a.

From the figure, we can see that OPSafe can survive the heap overflow attacks to make the web server continually serve the clients in the green zone with a modest performance degradation. Once closing the green zone, the web server still crashes when attacks occurring.

Performance Evaluation

We evaluated the normal execution overhead caused by OPSafe with these four applications. In this experiment, we use a ftp client to download a 300MB file from the ProFTPD server. For the web server Null-HTTPd, we use the Apache web benchmark ab to get the result. For the Email client Pine, we use it to send an email whose size is 9.5MB. For the GNU M4, we use its example test file foreach.m4 as the workload. We compared the average response time for server applications and the execution time for desktop applications.

We show the overhead of OPSafe in Figure 2b. It ranges from 8.77% for Null-HTTPd-df to 97.87% for GNU M4 with an average of 37.28%. Although OPSafe incurs a modest overhead, it provides a flexible protection mechanism with users' demand.

Related Work

In this section, we compare OPSafe with other solutions in preventing and responding to memory vulnerabilities attacks.

Proactive Defense Methods

Failure-oblivious computing [START_REF] Rinard | Enhancing Server Availability and Security Through Failure-Oblivious Computing[END_REF] tolerates memory vulnerabilities via manufacturing values for "out-of-bound read" and discarding "out-of-bound write". However, it should modify the source codes of the application with its specific compiler. Moreover, it may cause an unpredicted behavior which is an new threat for the application.

DieHard [START_REF] Berger | DieHard: Probabilistic Memory Safety for Unsafe Languages[END_REF] adopts the randomized allocation technique to give the application an approximation of an infinite sized heap, which can provide an high probabilistic memory safety. However, it should protect the application from the beginning and it is incapable for surviving stack smashing attacks.

Fail-stop Methods

There are a number of solutions proposed to defend against memory vulnerabilities in a fail-stop fashion, especially for stack smashing bugs. StackGuard [START_REF] Cowan | StackGuard: Automatic Adaptive Detection and Prevention of Buffer-overflow Attacks[END_REF] checks the integrity of canaries which are inserted around the return address. Address space layout randomization technique is proposed to protect applications against memory bugs exploits with a source-to-source transformation [START_REF] Bhatkar | Efficient Techniques for Comprehensive Protection from Memory Error Exploits[END_REF]. These solutions have to use the compiler to analyze or modify source codes via extending the GNU C compiler. However, OPSafe can protect applications without extending the compiler.

A binary rewriting defense technology [START_REF] Prasad | A Binary Rewriting Defense Against Stack Based Buffer Overflow Attacks[END_REF] is proposed to protect the return address. It inserts the return address defense codes into binaries of applications which can protect the integrity of the return address with a redundant copy. However, it is powerless for heap-related vulnerabilities.

Self-healing Methods

Rx [START_REF] Qin | Rx: Treating Bugs as Allergies-A Safe Method to Survive Software Failures[END_REF] combines the checkpoint/rollback mechanism and a changing execution environment to survive bugs. Especially for the stack smashing bugs, Rx drops the malicious users' requests.

ASSURE [START_REF] Sidiroglou | AS-SURE: Automatic Software Self-healing Using REscue points[END_REF] proposes the error virtualization and rescue point technique to bypass faulty region of codes. ASSURE may cause the application not function well, our previous works SHelp [START_REF] Chen | SHelp: Automatic Selfhealing for Multiple Application Instances in a Virtual Machine Environment[END_REF] applies weighted rescue points and extends it to a virtualization computing environment. However, all of these techniques unsafely speculate on programmer's intentions which may introduce new threats.

First-Aid [START_REF] Gao | First-Aid: Surviving and Preventing Memory Management Bugs During Production Runs[END_REF] tolerates a bug via identifying the bug types and bug-triggering memory objects, and generating runtime patches to apply them to a small set of memory objects. However, it cannot deal with the stack smashing bugs.

Conclusion

In this paper we present a new system OPSafe which can provide a hot-portable Green Zone of any size with users demand for applications where applications can safely survive memory bugs for a period of time from the starting or in runtime with users' demand. Once the green zone is opened, OPSafe takes over memory management of the application to make all the subsequent allocated memory objects including stack objects and heap objects reallocated and safely managed in a protected memory area, where the memory vulnerabilities can be prevented with high probability. Once closing the green zone, OPSafe clears away all objects in the protected area and then frees the protected area. We have developed a prototype system and evaluated the system's effectiveness using four applications with a wide range of memory vulnerabilities. The experimental results demonstrate that our system can conveniently create and destruct a hotportable green zone where the vulnerable application can survive crashes and eliminate erroneous execution.

Fig. 1 .

 1 Fig. 1. OPSafe Design

Fig. 2 .

 2 Fig. 2. OPSafe Evaluation

Table 1 .

 1 Applications and bugs used in evaluation

	Application Version Vulnerabilities ID	Bug	Description
	ProFTPD	1.3.3b	CVE-2010-4221	Stack Overflow	FTP Server
	Null-HTTPd Null-HTTPd-df	0.5.0	CVE-2002-1496 Manually Injected	Heap Overflow Double Free	Web Server
	Pine	4.44	CVE-2002-1320	Heap Overflow	Email Client
	M4	1.4.4	-	Dangling Pointer Macro Processor

Acknowledgment

This paper is supported by National High-tech R&D Program (863 Program) under grant No. 2012AA012600.


Guiyuan Jiang
email: jguiyuan@gmail.com

Jigang Wu

Jizhou Sun
email: jzsun@tju.edu.cn

Efficiency of Flexible Rerouting Scheme for Maximizing Logical Arrays

Keywords: Interconnection network, reconfiguration, rerouting scheme, fault tolerant, algorithm

In a multiprocessor array, some processing elements (PEs) fail to function normally due to hardware defects or soft faults caused by overheating, overload or occupancy by other running applications. Fault-tolerant reconfiguration considered in this paper is to reorganize fault-free PEs from a processor array with faults to a logical array of regular mesh topology by changing the interconnections among PEs. This paper presents the efficiency of the flexible rerouting scheme to maximize the usage of the fault-free PEs, by developing an efficient reconfiguration algorithm without backtracking. The proposed algorithm constructs each logical columns from left to right on candidate PE sets. It updates the candidate sets by excluding the PEs which cannot be used, once a logical column is formed. Also, it is proved that the proposed heuristic algorithm is able to generate the maximum-size logical array in linear time. Experimental results show that 123 logical columns can be constructed on 256 × 256 host arrays with fault density of 30%, resulting in an improvement of 51% in comparison to the previous algorithm by which only 82 logical columns can be produced. Furthermore, our algorithm is able to generate target arrays with harvest over 56% on host arrays with fault density of 50%, while the previous work cited in this paper fails to construct any target array in this case.

Introduction

The quest for high-performance and low-power leads to design multi-core architectures where an increasing number of processing elements (PEs) are integrated on a single chip in a tightly coupled fashion. In order to fully exploit the processing capabilities offered by the integration of an increasing number of PEs, on-chip communication networks play a critical role in developing high-performance embedded computing system. The option of reconfiguring the interconnect topology using optical circuit switches, which are of low-cost, low-power and highbandwidth, opens up new possibilities for improving not only the computing performance but also the reliability of multiprocessor systems.

To fully exploit the processing capabilities, many works have investigate application-aware topology reconfiguration techniques which try to customize the multiprocessor array to a topology that matches the traffic pattern of the application in order to reduce the power consumption and message latency etc. Optimizing network topology and mapping cores to network are two important application-specific reconfiguration methods. Topology determines the connectivity of the Network-on-Chip (NoC) nodes, while the core mapping tries to place the processing cores communicating more frequently near each other. The problem of topology selection and core mapping on NoC nodes have been explored to optimize an interconnection network based on a set of communication constraints by many researchers [START_REF] Murali | SUNMAP: A tool for automatic topology selection and generation for NoCs[END_REF] [START_REF] Bertozzi | NoC synthesis flow for customized domain specific multiprocessor systemson-chip[END_REF]. Reconfiguring the topology on NoC to reduce power consumption has been studied in [START_REF] Modarressi | Power-aware mapping for reconfigurable NoC architectures[END_REF]. And the work in [START_REF] Modarressi | Application-Aware Topology Reconfiguration for On-Chip Networks[END_REF] extends the paper [START_REF] Modarressi | Power-aware mapping for reconfigurable NoC architectures[END_REF] by proposing a more flexible and efficient structure and by providing extensive evaluations to thoroughly investigate the power, latency, and area of the reconfigurable NoC.

Since these fully customized topologies are designed and optimized for some specific applications, they give the best performance and power results only for that applications. The fault-tolerant reconfiguration considered in this paper is to re-organize the fault-free PEs in the multiprocessor array to a regular topology (standard structured) which ensuring well-controlled electrical parameters. Generally, two distinct types of fault-tolerant approaches, i.e. the redundancy approach and the degradation approach, are mostly investigated for processor array reconfiguration. The redundancy approach tolerates faulty PEs by replacing them with spare PEs [START_REF] Chen | A comprehensive reconfiguration scheme for fault-tolerant VLSI/WSI array processors[END_REF] [START_REF] Horita | Fault-tolerant processor arrays based on the 1.5-track switches with flexible spare distributions[END_REF], and if these PEs cannot replace all the faulty ones, the chip has to be discarded. In degradation approach, [START_REF] Kuo | Efficient reconfiguration algorithms for degradable VLSI/WSI arrays[END_REF] studied the problem of 2D mesh reconfiguration under three different routing constraints. They have shown that most problems that arise under these constraints are NP-complete and they also proposed some heuristic reconfiguration algorithms for these problems. An algorithm, namely GCR, was proposed in [START_REF] Low | On the reconfiguration of degradable VLSI/WSI arrays[END_REF] to find a maximal logical array (MLA) that contains a set of the selected rows. The techniques performing row-exclusion and compensation were proposed and combined with GCR into a heuristic algorithm to generate an approximate MLA [START_REF] Low | An efficient reconfiguration algorithm for degradable VLSI/WSI arrays[END_REF]. Recently, the power dissipation of a logical array was reduced in [START_REF] Wu | Reconfiguration Algorithms for Power Efficient VLSI Subarrays with 4-port Switches[END_REF] by reducing the number of long-interconnects utilizing a dynamic programming approach. In [START_REF] Fukushi | A genetic approach for the reconfiguration of degradable processor arrays[END_REF], a genetic algorithm (GA) for the reconfiguration of degradable mesh arrays is presented to evolve rerouting strategies for constructing logical rows/columns. In [START_REF] Wu | Preprocessing and Partial Rerouting Techniques for Accelerating Reconfiguration of Degradable VLSI Arrays[END_REF], novel techniques are presented to accelerate reconfiguration by employ flexible upper and lower bounds for the maximum logical array (MLA). The degradable reconfiguration approach for three-dimensional mesh-connected processor arrays is investigated in [START_REF] Jiang | Non-Backtracking Reconfiguration Algorithm for Three-dimensional VLSI Arrays[END_REF] [START_REF] Jiang | Efficient Reconfiguration Algorithm for Threedimensional VLSI Arrays[END_REF].

In a logical array, two neighboring PEs are interconnected through a group of physical links and these physical links form a interconnect path (interconnect for short) between the two PEs. Note that this architecture implements reconfiguration using simple switches, thus overlap of physical links is not allowed between any two interconnects, i.e., no physical link is shared by any two inter-connects of a feasible logical array. In order to generate logical arrays without overlap, most previous works develop reconfiguration algorithms under rerouting schemes with limitation on the routing distance d (see section 2.1 for formal definition), which means that if the distance between two PEs exceeds d, then the two PEs are not allowed to connect to form a logical array. This has brought convenience for designing reconfiguration algorithms, but it leads to large number of unused fault-free PEs, which is a serious waste of computing resources. This motivates us to increase the utilization of fault-free PEs by adopting flexible rerouting scheme. In this paper, we first investigate the performance loss of previous works in terms of utilization of fault-free PEs, then we adopt a flexible rerouting scheme in reconfiguration resulting in an efficient nonbacktracking algorithm, to produce maximum logical arrays under the rerouting scheme.

Preliminaries

Fault-tolerant Architecture and Rerouting Schemes

Let H denotes the physical (host) array on which some of the elements are defective due to hardware/circuit defects or soft faults which means temporary unavailability caused by overheating, overload or occupancy by other applications. Assume the fault density of the physical array is ρ, then there are N = (1-ρ)•m•n fault-free PEs in a m × n physical array. The rows and columns in physical array are called physical rows and columns respectively. A logical subarray which contains no faulty PEs constructed by changing states of reconfiguration switches is called a logical array (target array), denoted as T . The rows and columns in logical target array are called logical rows and columns respectively. Throughout this paper, e i,j (e ′ i,j ) indicates the PE located at the position of (i, j) of the host (logical) array, where i is its row index and j is its column index. row(u)(col(u)) denotes the physical row (column) index of the PE u. u=v denotes that u is identical to v.

Fig. 1 shows the fault-tolerant architecture for a 4×4 host array. The faulttolerant reconfiguration is achieved by inserting several reconfiguration switches in the network allowing the network to flexibly change the connections among PEs. Each square box in the host array represents a processing element (PE), whereas each circle represents a reconfiguration switch. In all figures in this paper, the gray shaded boxes represent faulty PEs while unshaded ones represent the fault-free PEs. There are 4 states for each switch.

In order to generate logical arrays without overlaps among interconnects, two software control schemes, i.e. bypass and rerouting schemes, are utilized to guide reconfiguration algorithms. In particular, row bypass and column rerouting schemes are mostly employed in previous works. As shown in Fig. 1, if PE e i,j is faulty, then PE e i,j-1 can communicate with PE e i,j+1 and data will bypass e i,j through an internal bypass link. This scheme is called row bypass. In column rerouting scheme, PE e(i, j) could connect to e(i + 1, j ′ ) by changing states of related switches where |j -j ′ | ≤ d and d is called the compensation distance [8][9]. If d is limited to 1, then PE e i,j can connect to one of the three PEs, i.e. e i+1,j-1 , e i+1,j and e i+1,j+1 , to form a logical column. The three PEs are called neighbors of e i,j , and set of the three PEs is denoted as Adj(e). column bypass and row rerouting schemes can be similarly defined. Generally, in order to reduce the complexity of the switching mechanisms and keep low cost of physical implementation, it is necessary to keep d small.

Construct Target Arrays on Selected Rows

Problem R. Given an m × n mesh-connected processor array in which some of its elements are faulty, find a maximum target array that contains the selected rows under the row bypass and column rerouting scheme.

Let R 1 , R 2 , . . ., R m be the rows of the given host array. Assume R r1 , R r2 , . . ., R rs are the s selected rows to construct a target array, where 1≤ r s ≤ m. Logical columns can be constructed under column rerouting scheme on selected rows, and interconnecting these logical columns under row bypass scheme forms a target array. A logical array T is said to contain R r1 , R r2 , • • • , R rs if each logical column in T contains exactly one fault-free PE from each of the selected rows. Note that, if a physical row is not selected for inclusion into target array, all PEs in the row will be bypassed.

Suppose C p and C q (C p ̸ = C q ) are two logical columns constructed on the s selected rows, thus each of them is consists of s PEs such that one and only one PE lies on each selected row. Let C p (i) denotes the PE lying in the i-th selected row of column C p and C q (i) denotes the PE lying in the i-th selected row of column C q , for (1 ≤ i ≤ s).

We say that C

p < C q if PE C p (i) in C p lies to the left-side of PE C q (i) in C q , for 1 ≤ i ≤ s. 2. We say that C p ≤ C q if PE C p (i) in C p lies to the left-side of, or is identical to, the PE C q (i) in C q , for 1 ≤ i ≤ s.
3. We say that C p and C q are independent of each other if C p < C q or C q < C p . 4. We say that C p and C q are overlap with each other if neither C p < C q nor C q < C p is satisfied.

We define that a logical column, say column C l , as the left-most column related to column set

A if C l ∈ A and C l ≼ C p for any C p ∈ A.
The problem R is proved to be optimally solved by an algorithm named Greedy Column Rerouting (GCR) [START_REF] Low | An efficient reconfiguration algorithm for degradable VLSI/WSI arrays[END_REF]. In fact, the target array produced by GCR is maximum-size under the constraint that the compensation distance d of columns rerouting scheme is limited to 1, instead of the maximum-size target array for the problem R. All operations in GCR are carried out on the adjacent sets of each fault-free PE u in row R ri , defined as Adj(u)={v : v ∈ R ri+1 , v is unused fault-free PE and |col(u) -col(v)| ≤ 1 }. Adj(u) consists of PEs that PE u can directly connect to in the next selected row. The PEs in Adj(u) are ordered in increasing columns index. The PE with the minimum column index in Adj(u) is called the leftmost connectable PE for u.

Flexible Rerouting Schemes

As we have discussed before, two types of software rerouting schemes, i.e. bypass and rerouting schemes, are employed to guide reconfiguration algorithms. In previous work, the compensation distance d of column rerouting scheme is limited to 1 to keep low cost of hardware implementation, thus 4-port switches are effective for reconfiguration. Rerouting schemes provides convenience for designing algorithms and guarantees that target arrays can be easily implemented using 4-port switches. However, there are considerable un-connectable PEs which are fault-free but cannot be used in forming a logical target array. Fig. 2 shows two logical arrays constructed from a 5×5 host array. Fig. 2(a) shows an logical array of two logical columns constructed by algorithm GCR under column rerouting scheme with d=1. The target array formed under flexible rerouting scheme contains 3 logical columns as shown in Fig. 2(b). There are 7 un-connectable PEs in the first target array, but only 2 un-connectable PEs is generated by adopting flexible rerouting scheme as shown in the second array.

Experimental results show that, under fixed column rerouting scheme with d = 1, the proportions of un-connectable PEs are up to 17.1%, 34.75% and 52.45% on 64 × 64 host array with fault densities are 10%, 20% and 30%, respectively. In order to to improve the harvest by reducing the number of unconnectable PEs, we adopt the flexible column rerouting scheme which is formed as follows. Assume that row R ri and R ri+1 are the i-th and (i + 1)-th selected rows, and set E i and E i+1 contain fault-free PEs in R ri and R ri+1 respectively, then a PE in E i can connect directly to any PE in E i+1 by reconfigure relative switch status.

Maximum-size Target Array under Flexible Rerouting Scheme

In this section, we solve problem R under flexible rerouting scheme to further increase target array size. In another word, given an m × n mesh-connected processor array H in which some of its elements are faulty, let R r1 , R r2 , ..., R rs be the selected rows, find a target array which consists of the maximum number of independent logical columns under the row bypass and flexible column rerouting scheme such that each logical column contains the selected rows. We first present a heuristic algorithm, denoted as FLX, which is capable of solving problem R in linear time. Then we prove that the target array constructed by FLX is maximum-size target array, and the target arrays constructed in this paper is much larger than that in previous works.

We model the problem R as follows. Suppose that set S contains all logical columns that can be construct on the selected rows of host array H. Formally, S={C|C is a logical column on selected rows and |C ∩ E i |=1 for 1≤i≤s}. Any column C in S contains exactly one PE from each selected rows. In problem R, we wish to find a maximum-size subset, say A, of independent logical columns.

We shall solve this problem in several steps, in each step we make choice of selecting one column for inclusion into A, and we are left with the subproblem S ′ : finding a maximum-size subset on subproblem S ′ . We observe that we need only to consider the greedy choice, the left-most logical column, in making each choice. Theorem 1 verifies that the greedy way of making choice leads to optimal solution, the verification is based on Theorem 2 which indicates that the greedy choice is always part of some optimal solution. Let S k = {C i |C i ∈ S and C k <C i } be the set of logical columns that lie to the right-side of column C k . If we make the choice of selecting the left-most column C 1 , then S 1 remains as the only subproblem to solve. Since C 1 is in some optimal solution, we can construct an optimal solution to the original problem consists of column C 1 and all logical columns in an optimal solution to the subproblem S 1 . In another word, {C 1 }∪A ′ is an optimal solution to original problem S if A ′ is an optimal solution to subproblem S 1 .

After constructing the leftmost column, some PEs becomes unconnectable due to overlap of interconnects. Rerouting on the unconnectable PEs leads to backtracking, such as in previous algorithm GCR. In order to improve the efficiency, we adopt the following technique to avoid backtracking. We identify unconnectable PEs so that columns containing unconnectable PEs will not be considered in the next stage selection. To exclude these un-connectable PEs out of sets E i for 1 ≤ i ≤ s, two type of situations are examined as follows, according to the newly constructed column C k . Let C k (i) and C k (i + 1) denote two PEs which lie in the ith selected row and the (i + 1)th selected row of column C k .

-case 1: col(C k (i + 1)) > col(C k (i)), then PE u is invalid if row(u) = r i , col(u) > col(C k (i)) and col(u) < col(C k (i + 1)). -case 2: col(C k (i)) > col(C k (i + 1)), then PE u is invalid if row(u) = r i+1 , col(u) > col(C k (i + 1)) and col(u) < col(C k (i)).
An example is shown in Fig. 3. u 1 is un-connectable according to case 1 and u 2 is un-connectable according to case 2. Thus, after constructing each left-most column, un-connectable PEs must be excluded from candidate PEs set. We implement the algorithm FLX in a iterative way instead of a recursive manner. The algorithm takes host array H with size of m×n in which some of its elements are faulty, and the indexes r 1 , r 2 , ..., r s that defines the selected rows as input. It returns a maximum-size subset of independent logical columns which form a logical target array T . The algorithm works as follows. The variable k indexes the most resent constructed left-most column,corresponding to the C k in algorithm FLX. Then the for loop initialize E i as the set of fault-free PEs in row R ri for 1 ≤ i ≤ s. PEs in E i are sorted initially by increasing column index. In while loop, the algorithm construct left-most column C k one by one and adds C k into target array T . In each iteration, the algorithm first construct a left-most column C k , then update candidate set E i (1 ≤ i ≤ s) by excluding un-connectable PEs according to C k . To see which PEs are un-connectable, two type of cases are examined as described above.

Now we analyze the complexity of the proposed greedy algorithm. Initialize candidate set Proof. Let C 1 be the left-most logical column in S, thus for any C p ∈S we have C 1 ≤C p . Then, based on theorem 2, there always exist an optimal solution, say A, whose left-most column is C 1 . Once the greedy choice C 1 is made, the problem S is reduced to find an optimal solution for subproblem S 1 = {C x |C x ∈ S and C 1 <C x } without have to consider any logical columns that overlap with C 1 in S 1 . This is because for any C p ∈S, we have C 1 ≤C p , and C 1 is the left-most column. Thus, all logical columns that are independent with logical column C 1 must not overlap with C 1 , i.e. they certainly belong to S 1 . Therefore, we can first construct the left-most column C 1 , and then try to find an optimal solution, say A 1 , for sub-problem S 1 , thus one optimal solution for the original problem S could be {C 1 } ∪ A 1 . In this way, we could find a maximum-size target array by making greedy choice at each step. In another word, algorithm FLX produces maximum-size target array for problem R. Theorem 2. Consider any nonempty subproblem S k , and let C m be the leftmost logical column on selected rows in S k . Then C m is included in some maximumsize subset of independent logical columns of S k .

E i (1 ≤ i ≤ s) runs in O(m • n).
if col(C k (i -1)) -col(C k (i)) > 1 then 23 for j ← col(C k (i)) + 1 to col(C k (i -1)) -
Proof Let A k be a maximum-size subset of independent logical columns in S k , and let C j be left-most logical column in A k . If C j =C m , we are done, since we have shown that C m is in some maximum-size subset of independent logical columns of

S k . If C j ̸ =C m , let the set A ′ k = A k -{C j } ∪ {C m } be A k but substituting C m for C j .

The logical columns in A ′

k are independent, which follows because the columns in A k are independent, C j is the left-most column in A k , and

C m ≤ C j . Since |A ′ k | = |A k |, we conclude that A ′
k is a maximum-size subset of independent logical columns in S k , and it includes C m . Therefore, C m is included in some maximum-size subset of independent logical columns of S k .

Experimental Results and Analysis

In this section, we investigate the efficiency of flexible rerouting scheme by evaluating performance of algorithm FLX in comparison with algorithm GCR. To evaluation metrics, i.e., harvest and degradation, as formulated in [START_REF] Low | On the reconfiguration of degradable VLSI/WSI arrays[END_REF][START_REF] Low | An efficient reconfiguration algorithm for degradable VLSI/WSI arrays[END_REF][START_REF] Wu | Reconfiguration Algorithms for Power Efficient VLSI Subarrays with 4-port Switches[END_REF][START_REF] Jiang | Non-Backtracking Reconfiguration Algorithm for Three-dimensional VLSI Arrays[END_REF][START_REF] Jiang | Efficient Reconfiguration Algorithm for Threedimensional VLSI Arrays[END_REF], were calculated. The harvest indicates how effectively the non-faulty elements are utilized in constructing a target array from a host array with fault elements, whereas the degradation measures the degree of potential performance loss due to a smaller target array than the original host array. For the simplicity, we denote target arrays constructed by algorithms GCR and FLX as GCRA and FLXA, respectively. The improvement in harvest of the FLX over algorithm GCR, is calculated by In order to make a fair comparison, we keep the same assumptions as in [START_REF] Low | On the reconfiguration of degradable VLSI/WSI arrays[END_REF][START_REF] Low | An efficient reconfiguration algorithm for degradable VLSI/WSI arrays[END_REF][START_REF] Wu | Reconfiguration Algorithms for Power Efficient VLSI Subarrays with 4-port Switches[END_REF][START_REF] Fukushi | A genetic approach for the reconfiguration of degradable processor arrays[END_REF][START_REF] Wu | Preprocessing and Partial Rerouting Techniques for Accelerating Reconfiguration of Degradable VLSI Arrays[END_REF][START_REF] Jiang | Non-Backtracking Reconfiguration Algorithm for Three-dimensional VLSI Arrays[END_REF][START_REF] Jiang | Efficient Reconfiguration Algorithm for Threedimensional VLSI Arrays[END_REF]. Faults are only associated with PEs and communication infrastructure is assumed to be fault free. This assumption can be justified since the switches and links use much less hardware resources when compared to the processors and are thus less vulnerable to defects. Both random fault model and clustered fault model were considered [START_REF] Kuo | Efficient reconfiguration algorithms for degradable VLSI/WSI arrays[END_REF][START_REF] Low | On the reconfiguration of degradable VLSI/WSI arrays[END_REF][START_REF] Low | An efficient reconfiguration algorithm for degradable VLSI/WSI arrays[END_REF][START_REF] Wu | Reconfiguration Algorithms for Power Efficient VLSI Subarrays with 4-port Switches[END_REF][START_REF] Wu | Preprocessing and Partial Rerouting Techniques for Accelerating Reconfiguration of Degradable VLSI Arrays[END_REF]. In a random fault model, the faults of a host array were generated by a uniform random generator. The fault density ρ of the host array is set from 5% to 30% for the experiments. On the other hand, without loss of generality, we model the clustered faults as a subarray that has 80% random faults in the host array. In order to focus on the clustered fault distribution, the fault density out of the subarray is set to 5%, which is far less than that in the subarray. The location of the subarray is generated randomly in the host array. Both algorithms were implemented in C++ language running on a computer with 2.1GHz CPU and 2GB RAM and are compared with each other on the same input instances. For each case, all physical rows are selected for inclusion into target array for experiments.

impr = harvest of FLXA -harvest of GCRA harvest of FLXA × 100%
Table 1 shows the performance comparison of algorithms FLX and GCR. For the case of constructing target array on 64×64 host array with fault density 10%, the harvest of target array produced by GCR is 82.91%, while it is 84.56% by algorithm FLX, thus resulting in the improvement of 2% in harvest. When the fault density increases to 30%, FLX improves GCR by 39.46% on harvest. It is because, with the increasing fault densities, more PEs become un-connectable in algorithm GCR while they can be used in FLX to form logical columns. It is also worth pointing out that, if the fault density exceeds a certain point, i.e. 50% for host arrays with size of 256 × 256, algorithm GCR fails to form any logical columns as shown in Fig. 4(a). However, algorithm FLX is still capable of constructing target arrays with no less than 70 columns which corresponding to a harvest of 56%, as shown in Fig. 4(b). On the other hand, on host arrays with large fault densities, the improvement in harvest is more significant on large target arrays than on the relatively small ones. For examples, with fault density of 30%, the improvements of FLX over GCR are 39.46%, 46.94% and 50.75% for host arrays with sizes of 64 × 64,128 × 128 and 256 × 256, respectively. It is because, the increasing size increases the difficulty of forming a logical column thus leads to decrease in the number of logical columns and results in increase in the number of un-connectable PEs. This provides more chance for algorithm FLX to improve the target arrays using flexible column rerouting scheme.

Table 2 shows performance gain of algorithms FLX over GCR for the case of the clustered faults on 512×512 host arrays with fault density 5%. Our investigations reveal that, the harvest improvement increased with the increasing number of clustered fault areas. For example, on host array with 24×24 clustered fault areas, the improvement of harvest is 5.15% for the case of 8 clustered fault areas, while it increased to 13.22% and 19.77% on host arrays with 24 and 32 clustered fault areas, respectively. This is because, as the number of clustered fault areas increases, fewer logical columns can be constructed by algorithm GCR, thus leads to more un-connectable PEs which provide more chance for optimization by FLX. In addition, the improvement for harvest decreases is more significant on relatively large clustered fault area. This is because logical columns constructed by GCR cannot go through clustered fault areas, thus large scale clustered fault areas decreases the area of PEs that can be used for constructing target arrays by algorithm GCR. On the other hand, large clustered fault areas increase the

Fig. 1 .

 1 Fig. 1. Switch functions and rerouting manners on a 4 × 4 mesh linked by four-port switches

Fig. 2 .

 2 Fig. 2. (a) only 2 logical columns are formed under column rerouting scheme with compensation distance d=1, (b) 3 logical columns can be constructed under flexible rerouting scheme.

Fig. 3 .

 3 Fig. 3. C1=<e1, e2, e3> is the left-most column, u1 and u2 become un-connectable after column C1 is constructed.

  Array Total number of Nonfaulty PEs in Host Array × 100% degradation = Size of Host Array -Size of Target Array Size of Host Array × 100%

Fig. 4 .

 4 Fig. 4. Comparison of FLX and GCR in terms of target array size and harvest, on host arrays of 256 × 256 with random faults, averaged over 20 instances for each case.

  In the while loop, each PE is Algorithm 1: FLX (H, r 1 , r 2 , ..., r s ) /* Flexible Column Rerouting Algorithm */ Input: host array H with size of m×n; indexes of selected rows: r1,r2,. . .,rs; Output: maximum-size target array T . ← set of fault-free elements in R ri ;

	1 begin
	2 for i ← 1 to s do
	4 k ← 1;	/* index of current logical column */
	5 while (E 1 ̸ = ϕ) do
	6	/* construct C k from candidate sets ∪ s i=1 Ei */

3 E i 7 for i ← 1 to s do 8 if (E i ̸ = ϕ) then 9 e ← the PE with minimum column index in E i ; 10 C k (i) ← e; 11 mark e as occupied; 12 else 13 stop the while loop; 14 /* exclude unconnectable PEs out of Ei(1 ≤ i ≤ s-1) according to case 1 */ 15

for i ← 1 to s -1 do 16 if col(C k (i + 1)) -col(C k (i)) > 1 then 17 for j ← col(C k (i))+1 to col(C k (i + 1))-1 do 18 if e i,

j ∈ E i then 19 mark e i,j as un-connectable; 20 /* exclude unconnectable PEs out of Ei(2 ≤ i ≤ s) according to case 2 */ 21 for i ← 2 to s do 22

1 do 24 if

  once, either to include into a left-most column or excluded out of candidate set E i , thus the while loop runs in O(m • n). Therefore, the algorithm FLX construct a maximum-size target array under flexible rerouting schemes in O(m • n) time.

	Theorem 1. Algorithm FLX produces maximum-size target array for problem
	R.

e i,j ∈ E i then 25 mark e i,j as un-connectable;

26 T ← T ∪ {C k }; 27 k ← k + 1; 28 return T ; examined only

Table 1 .

 1 The performance comparison of the algorithms GCR and FLX for random faults of uniform distribution, averaged over 20 random instances for each case.

	Host Array			Target array
	Size	Fault density	Array size GCR FLX	harvest (%) degradation (%) impr (%) GCR FLX GCR FLX
		0.05	64×54	64×55 89.23 89.64 15.23	14.84	0.46
	64×64	0.10 0.20	64×48 64×33	64×49 82.91 84.56 25.39 64×38 65.25 73.85 47.81	23.91 40.94	2.00 13.25
		0.30	64×21	64×30 47.55 66.08 66.72	53.75	39.46
		0.05	128×110 128×111 90.71 91.16 13.83	13.40	0.50
	128×128	0.10 0.20	128×96 128×98 83.29 85.20 25.04 128×68 128×77 66.55 75.64 46.76	23.32 39.49	2.30 13.74
		0.30	128×41 128×61 46.21 67.75 67.66	52.58	46.94
		0.05	256×222 256×224 91.41 92.06 13.16	12.54	0.72
	256×256	0.10 0.20	256×193 256×198 83.57 86.07 24.79 256×137 256×157 66.82 76.83 46.54	22.54 38.54	2.99 14.99
		0.30	256×82 256×123 45.65 68.75 68.05	51.88	50.75

Table 2 .

 2 The performance comparison of the algorithms GCR and FLX for clustered faults of uniform distribution on 512×512 host array, averaged over 20 random instances for each case. density of the host array, thus provide more chance for optimization by algorithm FLX.

	Host Array			Target array
	Cluster Distribution	Array size	harvest (%) degradation (%) impr
	size	number	GCR	FLX	GCR FLX GCR	FLX	(%)
		8	512×419 512×431 86.12 88.58 18.18	15.85	2.87
	16×16	16 24	512×400 512×419 82.25 86.09 21.87 512×381 512×409 78.42 84.06 25.50	18.21 20.15	4.72 7.23
		32	512×369 512×401 75.81 82.41 27.98	21.71	8.73
		8	512×395 512×416 81.29 85.44 22.77	18.83	5.15
	24×24	16 24	512×363 512×396 74.69 81.49 29.04 512×330 512×374 67.86 76.82 35.54	22.59 27.02	9.17 13.32
		32	512×294 512×351 60.40 72.13 42.62	31.47	19.77
		8	512×364 512×392 74.83 80.59 28.92	23.44	7.84
	32×32	16 24	512×318 512×364 65.40 74.79 37.87 512×251 512×322 51.54 66.27 51.04	28.95 37.04	14.78 28.80
		32	512×226 512×315 46.48 64.69 55.84	38.54	40.37

fault

ConclusionsMany previous works discuss the reconfiguration problems under column rerouting scheme with fixed compensation distance, resulting in great lose of harvest. This paper investigate the efficiency of flexible rerouting scheme by developing an efficient algorithm to reconfigure an multiprocessor array with faults. The proposed algorithm FLX is able to reduce the number of un-connectable PEs caused by the interconnection overlaps. It is capable of producing maximumsize target arrays, resulting in a significant improvement in comparison to the algorithm GCR. Experimental results show that the size of target array can be significantly increased. The algorithm FLX is scalable with the array size, as it is more efficient on large host arrays than on relatively small ones. In addition, its harvest tends to decrease slowly with the increasing fault density, that is superior to algorithm GCR whose harvest value decreases rapidly.

Acknowledgments.

This work was supported by the National Science Foundation of China under Grant No. 61070136 and No. 61173032, and the Doctoral Fund of Ministry of Education of China under Grant No. 20100032110041.


Weixing Ji

Yi Liu

Yuanhong Huo

Yizhuo Wang

Feng Shi

Extracting Threaded Traces in Simulation Environments

Keywords: program trace, full system simulation, multi-core processor

Instruction traces play an important role in analyzing and understanding the behavior of target applications; however, existing tracing tools are built on specific platforms coupled with excessive reliance on compilers and operating systems. In this paper, we propose a precise thread level instruction tracing approach for modern chip multi-processor simulators, which inserts instruction patterns into programs at the beginning of main thread and slave threads. The target threads are identified and captured in a full system simulator using the instruction patterns without any modifications to the compiler and the operating system. We implemented our approach in the GEM5 simulator and evaluations were performed to test the accuracy on x86-Linux using standard benchmarks. We compared our traces to the ones collected by a Pin-tool. Experimental results show that traces extracted by our approach exhibit high similarity to the traces collected by the Pin-tool. Our approaches of extracting traces can be easily applied to other simulators with minor modification to the instruction execution engines.

Introduction

Instruction trace characterizes a program's dynamic behavior and is widely used for program optimization, debugging and new architecture evaluation. Particularly, memory traces, which are subsets of instruction traces, are frequently used for new memory system evaluation. Program traces are also necessary for trace driven simulators, which is a well known method for evaluating new computer architectures. Prevailing tools for collecting application execution traces include tools built based-on Pin [START_REF] Bach | Analyzing Parallel Programs with Pin[END_REF] and Linux-process-tracker provided by the full system simulator Simics [START_REF] Virtutech | Simics User Guide for Unix 3[END_REF]. There are also a number of simulators and emulators available to generate traces on some platforms [START_REF] Binkert | The GEM5 simulator[END_REF][START_REF] Bellard | QEMU, a fast and portable dynamic translator[END_REF]. Theoretically, instruction traces can be extracted at virtually every system level, from the circuit and microcode levels to the compiler and operating-system levels [START_REF] Uhlig | Trace-driven memory simulation: a survey[END_REF]. However, existing trace collectors suffer from at least one of the following three limitations:

-Being highly dependent on operating systems and compilers and only available for one or two exiting platforms. It is difficult to add a new platform;

-Only supporting several existing ISAs, severely limiting the usage in new architecture exploration;

-Generating mixed instruction traces, which include instructions from other applications and operating system modules.

Tools built on Pin are efficient to collect traces for a single application, but it is only available for Windows and Linux running on IA-32 and x86-64. It is possible to port Pin to other platforms hosting a different operating system; and it is also possible to add a new back-end to Pin targeting a new processor family. However, this work would be time consuming and laborious. Pin-tools run as applications on existing platforms and this limits the usage when researchers are exploring new architectures. Some simulators, such as Simics features the functionality of single-process profiling only for Linux, while others, such as Solaris, are not supported at present. Besides, the techniques of instruction tracing in Simics are operating system dependent and the execution of scheduling module in the operating system triggers the tracing on and off. In case of an operating system update, the tracing functionality may lost their last straw to clutch at. The new simulator GEM5, which becomes increasingly popular in full system simulation, generates mixed instruction traces at present.

Uhlig [START_REF] Uhlig | Trace-driven memory simulation: a survey[END_REF] defines three aspects of metrics to evaluate the quality of traces and shows that the collected traces should be as close as possible to the actual stream of instructions made by a workload when running on a real system. In particular, the authors emphasize on the portability of trace collector. It should be easy to move the collector to other machines of the same type and to machines that are architecturally different. Finally, an ideal trace collector should be fast, inexpensive and easy to operate. In this paper, we propose a new approach to extract threaded traces in full system simulation environments that matches these criteria. This approach does not need to inspect the internal state of operating systems and does not need to change existing compilers.

In summary, this paper makes the following contributions:

-A new approach to extracting program traces in simulation environments.

It generates separated traces for each target thread and filters the noisy instruction sequences out.

-An efficient implementation of our approach in simulator GEM5 on x86-Linux. Evaluations on a suite of 7 benchmarks indicate that our approach is feasible and can be easily applied to other simulators.

The rest of this paper is organized as follows: Section 2 presents our new approach to extract thread level traces for applications in simulation environments. Section 3 shows our experimental results. Section 4 discusses the related work on trace extracting, and Section 5 concludes the paper.

Extracting Threaded Traces in Simulation Environments

Basic Idea

The basic idea of our approach lies in that a process is composed of one or more threads, and instructions executed on processors can be separated if all the threads of one process can be identified from the view of simulators. In general, thread IDs are software concepts and they are transparent to underline hardware in most implementations. Therefore, two issues should be addressed in this approach: (1) how to identify threads for a given process, and (2) how to find instructions executed by these threads.

In state-of-art operating systems, a process is a collection of virtual memory space, code, data and system resources. Although the internal presentation of threads and processes in operating system may differ from one to another, a process always has at least one thread of execution, known as the main thread or primary thread. Additionally, one or more threads can be created by the main thread and live within the same process. These slave threads share the same resources with the main thread. The running of a single process is represented as the execution of both main thread and slave threads. Namely, the traces of a process is actually the instruction sequences that are executed in these threads. One of the key issues is how to find the main thread and salve threads without the help of the operating system and compiler. We work out a solution to this problem using the stack pointer register (SP), which is explicit or implicit defined in most processors. Usually, at the creation stage, each thread is associated to a memory region referred to as thread stack. The primary purpose of this thread stack is used to store return address, pass parameters to the callee, store function local variables and so on. On the occasion of a function invocation, a new stack frame will be allocated for the execution of that function. When function returns, the caller or the callee is responsible to deallocated this stack frame by increasing or decreasing the stack pointer. Hence, the top of the stack dynamically changes from time to time and memory locations within the stack frame are typically accessed via indirect addressing.

For most operating systems and third-party thread libraries, a large memory block is usually allocated for each thread from the virtual memory space. The virtual address of the stack is not enough to distinguish the target threads from other threads created by other applications, as all the applications have the same size of virtual spaces starting from the same virtual address. However, these stack regions are mapped to different locations in the physical memory space. In general, the allocated virtual regions are large enough and programs do not change their location and size during runtime, and therefore threads can be distinguished using their stack positions in the physical memory space. However, this does not mean that all the physical addresses allocated to the stack can be considered as the unique identifiers of the target threads. The reason for this is that the virtual-to-physical mapping may change as the stack grows back and forth. Moreover, some of the physical pages may be swapped out and in during execution. However, we find that the first page at the bottom of the stack is always in use during the whole lifetime of a thread and most of existing operating systems provide APIs to prevent that part or all of the calling process's virtual address space from being paged to the swap area. If the first page at the bottom of the stack is locked into RAM and it is not remapped during execution, then virtual-to-physical mapping will not change. It is natural that we can use the first physical pages of stacks to distinguish threads of running processes. So long as we know which thread is running on the core, instructions can be captured and directed into different output streams.

How to Obtain Traces

The following presents a step-by-step explanation of the methodology for trace extraction in a simulated full system environment.

1. An instruction pattern is defined for the target program, which is delicately designed and composed of several instructions supported by target processors; 2. A predefined small function is executed at the beginning of every target thread. This function is used to: (1) lock the first page of thread stacks in memory and ( 2) execute the predefined instruction pattern; 3. The source code of the program is compiled using an existing compiler and translated into machine binary; 4. At the very beginning of thread execution, the first page at the bottom of each thread stack is locked in RAM, so that the physical page will not be swapped out at runtime; 5. The simulator snoops the instruction stream of each processor core and captures the patterns that are inserted into the application; 6. When the exact instruction sequence defined in the instruction pattern is captured, the starting address vaddrs and ending address vaddre of current stack in the virtual space are calculated according to the content of SP and the stack size. The physical address paddrs of vaddrs is also obtained through virtual-to-physical translation in the execution context of the processor core. We pack vaddrs, vaddre and paddrs up in a structure and insert it into a target thread list(ttl). 7. For each instruction executed by a processor core, the simulator reads the register SP to find out the virtual address where the top of current stack is. Then we go through the ttl and test the content of SP against each virtual stack regions recorded previously. If we find that SP is pointing to one of the virtual stack regions, we translate the vaddrs of the matched stack into its physical address paddrs ′ according to current execution context. If paddrs ′ is valid and equal to paddrs, which is obtained when the pattern is captured, then the instruction is included in the output trace.

In following discussion, we assume the starting address of a stack points to the location where the bottom of the stack resides, no matter which direction the stack grows to. Therefore, the mapping from virtual address vaddrs to physical address paddrs does not change for a thread from the beginning to the end and this paddrs can be used as the unique identifier of the target thread. Here, we need one more words for the calculation of vaddrs and vaddre before we proceed further. Given that the stack grows towards the lower address of the virtual space, these two addresses are calculated when the pattern is captured by:

vaddr s = vaddr sp -(vaddr sp mod ps) + (k × ps) -1 (1
)

vaddr e = vaddr s + 1 -ss (2)
where ps is page size and ss is stack size. k is an optional parameter and it is set to 1 in default. The reason why we can do this is that the instruction patterns are inserted at the beginning of both main and slave threads. We are certainly sure that the bottom of the stack is not far away from the address stored in the SP register when the pattern is captured. In general, there are 2 or 3 stack frames from the bottom to the frame that the pattern is capture. Hence, the distance from stack bottom to SP is no more than k pages. In most cases, the frame size of the thread function dose not exceeds the page size and k is set to 1. The starting address and the ending address of the stack can be calculated according to the size of the stack and the growing direction. The size of memory pages and the size of stacks are configurable and they can be easily figured out according to the version of the operating system and thread libraries.

To further present our idea clearly, a runtime scenario is given in Figure 1. As shown in the left part of this figure, two applications (App 1 and App 2 ) are started in the same operating system and run concurrently with 3 threads in total( 2 for App 1 and 1 for App 2 ). In this case, the virtual stack of thread T 1 may overlap the virtual stack T 3 because both App 1 and App 2 have private virtual spaces, which start from the same address and spread out for the same size. However, the three virtual pages at the bottom of these stacks are mapped to different physical pages as threads do not share stacks. Given App 1 is our target application and instruction patterns will be captured by the simulator at the beginning of threads T 1 and T 2 . At that moment, both SP 1 and SP 2 point to the first virtual page at the bottom of their stacks which are locked into RAM. Thus, vaddr1 s , vaddr1 e , vaddr2 s , and vaddr2 e can be calculated using equation 1 and 2. Meanwhile, paddr1 s and paddr2 s are obtained by address translation using vaddr1 s and vaddr2 s respectively. Right now, the target thread list ttl looks like {{vaddr1 s , vaddr1 e , paddr1 s }, {vaddr2 s , vaddr2 e , paddr2 s }}. The right part of this figure shows the extracting context of an instruction. Every time when an instruction is executed by some core in the simulator, only SP 4 is read and it is used to search ttl. In the case of virtual stack overlapping, the first element {vaddr1 s , vaddr1 e , paddr1 s } in ttl is tested and vaddr1 s is translated into physical address paddr1 ′ s in current execution context. However, it turns out that paddr1 ′ s = paddr1 s , which means current instruction is not belonged to any target threads. Therefore, the instruction is not included in the trace.

Instruction Patterns

The instruction pattern should be delicately designed, as the same sequence of instructions may appear in the execution of both applications and operating system modules. However, if the instruction sequence in the pattern is long enough, then there will be a small possibility that the same sequence of instructions exists in the original binaries. For example, following instruction sequence in Figure 2 is an example designed for programs running on x86. As multi-core processors are widely accepted and used now, applications running on an operating system tend to create multiple threads to fully utilize the hardware resource. It is important to have separated trace outputs for different threads, so that we get a precise instruction sequence for each thread. For this purpose, we pass the thread ID(tid in the last line of Figure 2) to the runtime in the pattern in a known register. This tid can be read from that register at the time when the pattern is captured by the simulator. Then it is stored in the ttl and used as an identifier for a target thread. Similarly, it is also possible to assign different thread IDs to different applications. In such a way, we can start and run multiple applications simultaneously in a system and have separated traces for all the threads created by all target applications. This feature is especially useful to analyze the dynamic execution interferences among multiple applications.

Our approach requires the user to insert instruction patterns into their source code and start the simulator with the pattern as an input. It can be implemented in most full system simulators without modifications to the compiler and the operating system, as the default size of thread stacks usually does not change. Even though the size is changed or the thread function has a very large stack frame, setting a new size in the configuration file will be able to extract correct __asm__ __volatile__ ("move %0, %%eax\n\t" "add $0x0, %%eax\n\t" "add $0x0, %%eax\n\t" : : "r"(tid) ); Fig. 2. Instruction pattern for x86-Linux traces. Our approach still work well in case of system updates, because it is not necessary to inspect the internal state operating systems.

Evaluation

Evaluation Method

GEM5 is a modular platform for computer system architecture research, encompassing system-level architecture as well as processor microarchitecture [START_REF] Binkert | The GEM5 simulator[END_REF]. GEM5 provides a highly configurable simulation framework, multiple ISAs, and diverse CPU models. Our experiments were performed on x86-Linux, as it is well supported and widely used. We lock some pages of a process's virtual address space into RAM, preventing these pages from being paged to the swap area. In our implementation, mlock is invoked at the very beginning of each thread to lock the identification pages at the bottom of thread stacks in RAM, so that each identification page is guaranteed to be resident in RAM and mapped to a same physical page before thread termination.

We also built an instruction tracing tool based-on the framework provided by Pin. In our experiments, we compared our traces to the ones obtained by the Pin-tool on x86-Linux. To further verify the effectiveness of our approach, we run multiple benchmarks together and generate separated traces for each application in GEM5. These traces are then compared with the traces generated by the Pin-tool. Taking 4 applications (a, b, c and d) for example, we run the applications in the simulator one at a time and get four traces(a 1 , b 1 , c 1 and d 1 ), then we partition the benchmarks into 2 groups( (a,b), (c,d)), and start the two benchmarks in the same group at the same time in the simulator. Then we extracted another four traces(a 2 , b 2 , c 2 and d 2 ) from the hybrid instruction streams. After that, we compared the two traces of each benchmark with their Pin-tool counterparts to see how similar they are.

Even though the simulated x86-Linux is different from the host machine in many aspects, we expect highly similar traces for a same executable binary. This is because the difference in microarchitecture dose not changes the order of instructions in the same thread; however, in effect, they are not exactly the same due to thread scheduling and synchronization. The operating system images and compilers are all provided by the GEM5 team and we didn't make any modifications to these system software. All the benchmarks are compiled with the "-static" options to make sure that no differences will be introduced into the traces by using different dynamic loaded libraries. Meanwhile, the instruction patterns are labeled by the #pragma OPTIMIZE OFF and #pragma OPTIMIZE ON pair to turn off GCC optimizations in these regions. This optimization restriction prevents the instructions in the pattern being removed or reordered, otherwise, the patterns can not be captured in the simulator while applications are running.

We use the standard multi-thread benchmarks to evaluate our approach, and all of the programs are selected from SPLASH2 [START_REF] Woo | The SPLASH-2 programs: Characterization and methodological considerations[END_REF]. For each application, only three lines of codes are inserted into the original sources: 1) including a head file defining the patterns, 2) inserting the pattern at the beginning of the main thread, and 3) inserting the same pattern at the beginning of slave threads. After that, all the benchmarks are compiled and each binary is executed on the host machine and the simulated full system in GEM5 separately. All the benchmarks we used are listed in table 1.

Results

Figure 3 and4 show the calculated similarity between two traces collected by hacked GEM5 and Pin-tool respectively. Call traces are reduced instruction traces that only contain instructions of function calls and returns. All the GEM5 traces are collected in solo-runs in the simulated full system. It shows that our traces are much similar to the ones collected by the Pin-tool. Though the the similarity of call traces is as high as up to 90% for most benchmarks, the instruction traces exhibit a relative low similarity around 85%. The reason for this is that the hacked GEM5 only starts to generate traces after instruction patterns are captured. Hence, the instructions executed at the startup phase before the main function are not included in the GEM5 traces, which add up to about 10 thousands in total. Meanwhile, we found that the difference is slightly enlarged as the number of threads increases. In order to find out the differences for the two call traces, the edit sequence for the two traces is rebuilt. From the edit sequence, we found the benchmarks with multiple threads spent much longer time at the synchronization points than their sequential versions. The threads, which run faster than others are scheduled out and in from time to time, execute a number of instructions to check the status of barriers. Even though multiple applications are started to run at the same time, our approach is capable of distinguishing one application from another with different thread IDs. We partition all the benchmarks into 3 groups. Each group has 2 or 3 benchmarks and all the benchmarks in one group are started together in the same simulated full system. The hacked simulator generated separated traces for each application. The partition of groups is given in table 1 and the calculation results for the two platforms are shown in Figure 5 and6. Note that each instruction and call trace extracted from GEM5 in co-runs are compared with their counterparts collected by the Pin-tool in solo-runs. All the benchmarks in the same group were started with 1-16 threads and the simulated system was configured with 4 physical cores. Hence, target threads are swapped in and out frequently at runtime because the number of threads is much larger than that of available cores. The calculated results for instruction traces are very close to each other.

Related Work

Many approaches have been in use for obtaining low level instruction traces for applications, including dynamic instruction instrumentation, exploiting of hardware performance counters, utilization of the hardware monitor and instruction simulators or emulators [START_REF] Uhlig | Trace-driven memory simulation: a survey[END_REF]. Anita et. al. built a system for generating and analyzing traces based on link-time code modification [START_REF] Borg | Generation and analysis of very long address traces[END_REF], which makes the generation of a new trace easy in early days. Their system was designed for use on RISC machines and on-thefly analysis removes most limitations on the length of traces. Binary dynamic instrumentation tools such as Pin [START_REF] Luk | Pin: building customized program analysis tools with dynamic instrumentation[END_REF], and other similar tools can collect application instruction traces by modifying the application instruction stream when running. Some tracing tools can be easily built with Pin and it widely used by researchers to obtain traces on IA-32 and x86-64.

Full system simulators and emulators, such as Simics [START_REF] Virtutech | Simics User Guide for Unix 3[END_REF], GEM5 [START_REF] Binkert | The GEM5 simulator[END_REF], and QEMU [START_REF] Bellard | QEMU, a fast and portable dynamic translator[END_REF], have the ability to collect instruction traces. But limitations can be found as well. The Linux-process-tracker is a Simics-provided module that allows tracking user-specified processes by either process id (pid) or file name in Linux [START_REF] Chen | SimSight: a virtual machine based dynamic call graph generator[END_REF], which inspects the simulated operating system and calls the callback functions when interesting things occur. The GEM5 simulator is a modular platform for computer system architecture research, encompassing system-level architecture as well as processor microarchitecture [START_REF] Binkert | The GEM5 simulator[END_REF]. It is widely adopted in ar-chitecture research and does offer detailed instruction trace functionality mainly for debugging purpose. QEMU is a fast processor emulator using a portable dynamic instruction translator [START_REF] Bellard | QEMU, a fast and portable dynamic translator[END_REF]. It supports many ISA(x86, ARM, MIPS,etc) both on host and guest sides and also can run in full system emulation mode. QEMU has the ability to generate memory traces.

Researchers in application profiling and performance optimization have proposed several tools and frameworks that exploit hardware devices such as hardware performance counters to collect performance data [START_REF] Browne | A scalable crossplatform infrastructure for application performance tuning using hardware counters[END_REF]; while others built hardware devices [10] [11] [12] [13] to accomplish this work. With the help of these tools, researchers can collect application traces fast and accurately. Unfortunately, these equipments are either expensive or complicated to be set up and therefore cannot be widely used.

Conclusion

Traces record all the information about a program's execution in the form of instruction sequences. In this paper, we propose a new approach to extract threaded traces for applications in full system simulation environments. Traces of each application are extracted from the instruction stream blended with instructions from operating system modules and other applications. Each thread in a given application is identified by an instruction pattern without inspecting the internal state of the operating system. Our approach can be applied to existing full system simulators with no changes to compilers. We implemented our instruction extraction approach in the simulator GEM5 and performed a number of experiments on the simulated full system x86-Linux. Experimental results show that traces extracted by our approach exhibit high similarity to the traces collected by a Pin-tool.

Fig. 1 .

 1 Fig. 1. Stack mapping and identification in simulation

Fig. 3 .

 3 Fig. 3. Instruction trace similarity for solo-runs

Fig. 4 .

 4 Fig. 4. Call trace similarity for for solo-runs

Table 1 .

 1 Benchmarks

	Benchmark	Description	Group
	fft	A 1-D version of six-step FFT algorithm.	1
	lu-non	Dense matrix factoring kernel.	1
	radix	Integer radix sort kernel.	2
	lu-con	Dense matrix factoring kernel.	2
	fmm	Body interaction simulation.	3
	ocean	Large-scale ocean movements simulation.	3
	ocean-non Large-scale ocean movements simulation.	3