Ray C C Cheung
email: r.cheung@ic.ac.uk

Wayne Luk
email: w.luk@ic.ac.uk

Peter Y K Cheung
email: p.cheung@ic.ac.uk

Reconfigurable Elliptic Curve Cryptosystems on a Chip

This paper presents a System-on-a-Chip (SoC) architecture for Elliptic Curve Cryptosystems (ECC) which targets reconfigurable hardware. A four-level partitioning scheme is described for exploring the area and speed tradeoffs. A design generator is used to generate parameterisable building blocks for the configurable SoC architecture. A secure web server, which runs on a reconfigurable softprocessor and an embedded hard-processor, shows over 2000 times speedup when the computationally-intensive operations run on the customised building blocks. The embedded on-chip timer block gives accurate performance information. The design factors of configurable SoC architectures are also discussed and evaluated.

Introduction

Field Programmable Gate Arrays (FPGAs) enable a high degree of parallelism and can achieve orders of magnitude speedup over general purpose processors [START_REF] Batina | Hardware architectures for public key cryptography. Integration[END_REF]. Many applications such as signal, image, video, networking and security have been successfully mapped into reconfigurable hardware, for exploring the on-chip parallelism and achieving design flexibility. As the design moves to systemlevel integration, the control logic and the computationallyintensive logic are usually separated. Configurable Systemon-Chip (CSoC) devices [START_REF] Becker | Configurable systems-on-chip (CSoC)[END_REF][START_REF] Knapp | Field configurable SoC device architecture[END_REF], which are a combination of embedded microprocessors, memory and embedded programmable logic, have attracted academic research and also resulted in industrial products such as Triscend A7, Xilinx VirtexII Pro and Altera Excalibur. Each of them has one or more embedded microprocessors using different instruction set architectures at different clock speeds, and large programmable logic resources. Previous work mainly focuses on the speedup from using pure FPGAs over processors, and analyses the mapping from different application domains to different configurable resources [START_REF] Guo | A Quantitative Analysis of the Speedup Factors of FPGAs over Processors[END_REF].

In this paper, we aim to explore the huge design spaces provided by CSoC devices, to describe the limiting factors in designing CSoC applications and to predict the dominat-ing factors as the technology grows. It is clear that in this design space, the two extreme cases are the pure software implementation running on a generic processor which has no additional area overhead, and the hardware implementation purely running on configurable logic which gives the best performance but uses the largest area. As shown in Figure 1, the software program can be run on a PC or an embedded processor, or the design could be fully mapped into hardware. On the other hand, there are several design parameters such as the processor speed, the reconfigurable logic speed, the memory speed and the CoreConnect [START_REF]Embedded System Example: Web Server Design Using MicroBlaze Soft Processor[END_REF] bus speed connecting the processor and user logic. We define Intellectual Property (IP) block as a building block which contains customisable user logic. In this paper, we address the following two questions:

1 How much application logic should we put into the reconfigurable fabric?

2 What are the limiting factors on the performance for a CSoC design; in particular, which factor dominates? Elliptic curve cryptography (ECC) is a public key cryptography system superior to the well-known RSA cryptography: for the same key size, it gives a higher security level than RSA [START_REF] Batina | Hardware architectures for public key cryptography. Integration[END_REF]. ECC has been adopted in a wide variety of applications from digital certificates in webserver authentication [START_REF] Gura | An End-to-End Systems Approach to Elliptic Curve Cryptography[END_REF] to embedded processors in wearable devices. A major trend of research work is hardware acceleration, and some recent work addresses system integration [START_REF] Gura | An End-to-End Systems Approach to Elliptic Curve Cryptography[END_REF][START_REF] Nguyen | Implementation of Elliptic Curve Cryptosystems on a Reconfigurable Computer[END_REF] using the PCI interface and proprietary interconnect. In this paper we propose an SoC approach and evaluate the effect of partitioning in a single chip. Our main contributions include:

A building block containing a field multiplier where degree of parallelism can be varied (Section 3).

Customisable IP blocks for four-level partitioning of ECC operations (Section 3).

An SoC architecture and design generator for ECC IPs incorporating embedded processors (Section 4).

Performance evaluations of individual IP blocks and the configurable SoC chip (Section 5).

The rest of the paper is organized as follows. Section 2 describes related work on ECC. Section 3 presents the architectures of the relevant customisable IP blocks. Section 4 describes the design generator of our approach, and the system integration between IP blocks and embedded microprocessors. Section 5 evaluates our results and compares the software and hardware designs. Section 6 describes a framework of a secure web server system running on the CSoC chip. Finally, Section 7 summarises our current and future research.

Background and Related Work

The difficulty of the underlying Elliptic Curve Discrete Logarithm Problem (ECDLP) makes ECC cryptosystems suitable for applications that need long-term security and low bandwidth measurements. For instance, the NIST has recommended specific curves for implementations [12] and the IEEE has provided detailed specifications for the choices of private key length and fields [START_REF] Batina | Hardware architectures for public key cryptography. Integration[END_REF].

ECC research can be first divided into two groups depending on the underlying field representation: prime field, GF (p) and binary field, GF (2 m ). Two bases, Optimal Normal Basis (ONB) and Polynomial Basis (PB), are commonly used for manipulating binary fields. It is known that the binary field is more suitable for hardware implementation, and squaring is very fast using ONB. However, point multiplication requires efficient design for field multiplication, inversion, squaring and efficient coordinate systems. In recent years, there has been much software [START_REF] Hankerson | Software implementation of elliptic curve cryptography over binary fields[END_REF] and hardware [START_REF] Orlando | A High Performance Reconfigurable Elliptic Curve for GF (2 m )[END_REF] research work on both GF (p) and GF (2 m ) focusing on the performance of point multiplication, and it is obvious that a fast point multiplication design is crucial.

Previous hardware work includes: the first ASIC design with a Motorola M68008 microcontroller which calculates 9 point multiplication per second, an ECC design on a 8051 microprocessor in smart cards, and recent FPGA implementations for ECC designs [START_REF] Leong | A Microcoded Elliptic Curve Processor using FPGA Technology[END_REF]. System level work has also been reported such as a secure web server [START_REF] Gura | An End-to-End Systems Approach to Elliptic Curve Cryptography[END_REF] and a reconfigurable computer [START_REF] Nguyen | Implementation of Elliptic Curve Cryptosystems on a Reconfigurable Computer[END_REF]. In this paper, we build a flexible CSoC using configurable logic and embedded processors, and apply it to applications such as a secure web server system.

Design Partitioning

This section describes the operations in our ECC architecture using GF (2 m ) with ONB. Section 3, 4, 5 use a bottom-up approach, we first break down the ECC operations and put them into IP blocks in Section 3, then describe the design flow and how we construct the hardware architecture in Section 4. An overview of the interactions amongst ECC routines is shown in Figure 2. Our architecture supports point multiplication, addition and substraction, in this paper we focus on the design partitioning of point multiplication. The arrows in the figure show the dependencies amongst different operations.

Level 1 -Pure Software

In this paper, we adopt the open source software from Rosing [START_REF] Rosing | Implementing Elliptic Curve Cryptography[END_REF]. The basic routines such as the field and point multiplications are implemented in C and compiled for both Pentium PC and embedded processors. Table 1 shows the number of field multiplications and field inversions for one point multiplication. By using this information, we can evaluate the effect of replacing the software routine by configurable logic.

Level 2 -Field Multiplication

In our ECC cryptosystem, the field multiplier as shown in Figure 3 is based on our previous work [START_REF] Telle | Customising Hardware Designs for Elliptic Curve Cryptography[END_REF]. This field multiplier is repeatedly used by other operations as shown in Figure 2. The datapath of our system for various operations is shown in Figure 4. For the pure hardware architecture, users are able to select the second level paral-lelism in terms of the number of executable field multipliers up to a maximum four parallel field multipliers. Different scheduling optimizations have been applied to the corresponding designs. Using more than four field multipliers does not bring further speed improvement but induces an area penalty. There is a tradeoff between efficiency and area, and the designer must select the best design. Since field multiplication is the most computationallyintensive operation, we separate and build it as a single IP block using the design flow as shown in Figure 5. The inputs to this block are two m-bit values, and another m-bit data are generated at the end of the computation.

Level 3 -Field Inversion

In level 3, we develop an IP solely for computing field inversion. The algorithm we used for field inversion is based on the Fermat's theorem which states that in a normal basis:

a 1 = a 2 m 2 = (a (2 m 1 1) ) 2
The pseudo-code for this field inversion can be found in our previous work [START_REF] Telle | Customising Hardware Designs for Elliptic Curve Cryptography[END_REF]. The basic idea is to find an inverse m-bit field element by inputting an arbitrary m-bit field element. In this field inversion block, the field multiplication circuit described in level 2 is reused and is placed as a component inside this block.

Level 4 -Point Multiplication

Point multiplication is the key operation in ECC and it is the most time-consuming process. We adopt the improved Montgomery Scalar multiplication [START_REF] López | Fast multiplication on elliptic curves over GF (2 m ) without precomputation[END_REF] in our design. In our embedded logic core, users are able to preload some of the system options such as the base point and the curve information. This could save time as the basic point multiplication "Q = k P" where P = P (x, y) that has two components. The bus width of our prototyping platform is 32-bit, as a result, the k and P values are tokenized and then sent between the embedded logic and the embedded processor.

Design Generator

In this section, we describe a design generator that produces high-level Handel-C code for arbitrary field size and degree of parallelism. The generated Handel-C is then translated into VHDL; we use a developed wrapper to connect this user logic with the interface connect core. As shown in Figure 5, the customised IP block is thus connected to the bus with its own address space such that the embedded processor can directly send data to it. The system overview that makes use of embedded processors and configurable logic IP blocks which are generated in the design flow. As shown in Figure 6, the On-Chip Peripheral Bus (OPB) provides a fast link between logic cores such as the configurable user IP block and the on-chip timer. The PowerPC processor is first connected to the highspeed Processor Logic Bus (PLB) and then uses a bridge to connect to the OPB peripherals.

Performance Evaluation

The results are divided into two parts. (1) Evaluation of a standalone ECC IP block using the Celoxica RC2000 board containing an XC2V6000 FPGA chip. This compares the speed of point multiplication using different hardware and software. (2) Evaluation of the CSoC design using the Xilinx ML310 board containing an XC2VP30 FPGA chip. This compares the speed of implementing different IPs using configurable logic. The reported timing information and area usage are collected from the Xilinx place-and-route tools and the OPB on-chip hardware timer.

Individual IP Block

We compare the performance of various software and hardware implementations for point multiplication, which is the bottleneck for ECC systems. We have implemented the software design [START_REF] Rosing | Implementing Elliptic Curve Cryptography[END_REF] on a dual-processor Intel Xeon 2.66GHz with 4GB of RAM. The comparison for serial and parallel designs on different m and p values, where p refers to the degree of parallelisation, is presented in Table 2. Note that Place-and-Route (P&R) results refer to those obtained from the Celoxica DK3 and Xilinx ISE 6.2 tools, and measured results refer to those from hardware realisation. We have also verified each design using 300,000 consecutive point multiplications using data sent and received from the PC. The "Speedup" column shows the performance gain of our design over other methods. This gain is due to our highly parallel architecture which does not involve instruction fetch and decode. As shown in Figure 7, the area requirements for various designs such as m = 113, 162 using 1, 2 and 4 field multipliers (1FM, 2FM and 4FM) show a linear growth when the degree of parallelism p increases. The speed for performing one point multiplication is shown in Figure 8 with respect to four different cases: m is not divisible by p using 1FM, m is divisible by p using 1FM, 2FM and 4FM. The ECC IP block designed in this paper is highly customisable and can cope with different area and speed tradeoffs.

CSoC Design

Figure 9 shows the speed of field multiplication and field inversion for different m values using the embedded Pow-erPC. We can see that the time spent on one inversion grows faster than that on field multiplication. We also measure the time for transferring one data item and for transferring 1000 consecutive data items using the CoreConnect bus. From Table 3, the overhead of consecutive transfers is smaller. The measured speed by using configurable logic for different levels are given in Table 4, 5 and 6. Note that the cycle count starts once the processor enables the operation and ends when a "done" signal is received from the configurable logic. The software running on the embedded processor is responsible for controlling data transfer.

Parallelism

P&R results

Measured results Software [START_REF] Rosing | Implementing Elliptic Curve Cryptography[END_REF] Hardware (serial) [ In Table 5, the required I/O cycles mean that in order to replace the software routine by programmable logic, four read cycles and four write cycles are needed. We can see that if the operation performed in logic is very fast and the I/O transfer cycles will dominate this overhead. In Table 4, there is actually no performance gain when the degree of parallelism is equal to or larger than four. On the other hand, there is no I/O overhead for the result using embedded microprocessor. In Table 4, we use the on-chip timer to measure the number of cycles taken to perform one field multiplication for both embedded processor and the IP block.

Technology Trend Discussion

The limiting factors of most CSoC systems are the speed of configurable logic, speed of the bus or switch connecting between the embedded processor and the configurable logic, the speed of embedded processors and the memory bandwidth. As shown in our results, the major bottleneck of the CSoC designs is the bandwidth and the latency of the bus connecting the embedded processors and the configurable logic. For instance, an elliptic point in the size 113 field needs to be divided into eight 32-bit words for data transmission. As shown in Table 3, each single R/W operation takes 100 cycles of embedded on-chip timer that is very expensive in high performance applications. We expect that using a wider bus-width in CSoC is the major trend.

Our results show that the clock speed of all synthesized designs is around 70-90MHz which is slower than the embedded processors. The next generation reconfigurable logic is able to achieve up to 500MHz and it will enlarge the forementioned bottleneck. For the memory bus, many systems use the CoreConnect/AMBA bus for connecting the embedded memory and the microprocessors. We expect that a wide low-latency bus, which is tightly coupled the processor, memory and configurable logic will be crucial.

Secure Web Server

A secure web server using our CSoC framework is depicted in Figure 10. In this system, a network logic core [START_REF]Embedded System Example: Web Server Design Using MicroBlaze Soft Processor[END_REF] is added to the OPB bus for communicating between the web server program running on the embedded processors and the network. From Table 6, a speedup factor of 2000 is achieved when we replace the m = 113 point multiplication running on the embedded processor by the customised level 4 IP block including the read/write bus overheads. We also illustrate that our CSoC chip can benefit another secure web service. Previous work [START_REF] Gura | An End-to-End Systems Approach to Elliptic Curve Cryptography[END_REF] describes an ECC hardware system that accelerates the Secure Socket Layer (SSL) in a client/server system. The ECC keys are embedded into the generated X.509 certifcates. Their implementation involves an FPGA on a PCI bus at 66.4MHz, and achieves 12.5 times speedup for the Elliptic Curve Key exchange when comparing with pure software implementation. Since the point multiplication in our design is twice as fast, our design could achieve up to 25 times speedup.

Conclusions

This paper presents a configurable SoC architecture for Elliptic Curve Cryptosystem and an embedded secure web system using reconfigurable hardware. A four-level partitioning scheme is proposed for exploring the area and speed tradeoff of pure software implementation on embedded processor and the customisable building blocks approach. Our experience shows that performance in CSoC designs is dictated mainly by data transfer speed, hence it is desirable to have a wide bus-width and a wide memory bus with low latency for most embedded system designs. Future work includes CSoC designs for other application domains and the use of run-time reconfiguration.

Figure 1 :

 1 Figure 1: The limiting factors for Configurable SoC.

Figure 2 :

 2 Figure 2: Interactions between different operations.

Figure 3 :

 3 Figure 3: Parallel field multiplier IP block.

Figure 4 :

 4 Figure 4: Datapath of the customisable ECC system.

Figure 5 :

 5 Figure 5: Diagram of the design flow.

Figure 6 :

 6 Figure 6: Architectural components in a single chip.

Figure 7 :

 7 Figure 7: Area usage for various p and m values.

Figure 8 :

 8 Figure 8: Speed comparison for various p and m values.

Table 6 :

 6 Level 4: Comparison of one point multiplication when m = 53 (I/O cycles: 6W+4R) and m = 113 (I/O cycles: 12W+8R) using one field multiplier.

Figure 10 :

 10 Figure 10: Secure web server overview.

Table 1 :

 1 Statistics of field multiplication and field inversionfor different field size m.

	field size m	53	113	131	233	270
	no. of multiplications	612 1530 1760 3732 4758
	no. of inversions	68	153	176	311	366

Table 2 :

 2 Comparison between our design and the reference designs[START_REF] Leong | A Microcoded Elliptic Curve Processor using FPGA Technology[END_REF][START_REF] Rosing | Implementing Elliptic Curve Cryptography[END_REF]. The symbol (*) denotes extrapolated results based on published data for different m values.

	9]

Table 3 :

 3 Read/Write cycles using the CoreConnect bus, sharing reduced cycles for multiple Read/Write.

	parallelism	1	2	4	8	16
	cycle count	297	239	181	181	181
	speed (us)	3.15	2.62	1.99	1.92	2.18
	area (slices)	2063 2199 2487 2691 3494
	embedded PowerPC		117591 cycles

Table 4 :

 4 Level 2: Comparison of one field multiplication when m = 113 (I/O cycles: 8W+4R).

	parallelism	1	2	4	8	16
	cycle count	1109	703	471	355	297
	speed (us)	13.70	8.78	4.99	3.94	3.87
	area (slices)	2708	2966 3251 3528 4299
	embedded PowerPC		972098 cycles

Table 5 :

 5 Level 3: Comparison of one field inversion when m = 113 (I/O cycles: 4W+4R).

		0.045
							field multiplication
								field inversion
		0.04
		0.035
		0.03
	speed: second	0.02 0.025
		0.015
		0.01
		0.005
		0
		40	60	80	100	120	140	160	180	200
						field size: m
	Figure 9: Level 1: OPB Timer block measurement of Pow-
	erPC running at 300MHz designs.
			parallelism		1	2		16
					m = 53
			cycle count		19411	16555	3603
			speed (us)		206.04	175.63	47.09
			area (slices)		3712	3869	4529
		embedded PowerPC		19591629 cycles
					m = 113
			cycle count		79761	42767	9875
			speed (us)		1021.82 570.73 123.01
			area (slices)		6001	6344	7677
		embedded PowerPC		166950475 cycles

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

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)

Acknowledgement. Thanks to Dr T. Todman and the referees for comments, and to the Croucher Foundation for support.


Olivier Beck

Martin Barondeau

Frank Kaibel

Poehl

Logic Design for On-Chip Test Clock Generation -Implementation Details and Impact on Delay Test Quality

Thispaper addresses delay testfor SOC devices with highfrequency clock domains. A logic design for onchip high-speed clock generation, implemented to avoid expensive test equipment, is described in detail. Techniques for on-chip clock generation, meant to reduce test vector count and to increase test quality, are discussed. ATPG results for the proposed techniques are given.

1 Introduction Structural testing of digital integrated circuits already has a long tradition in the semiconductor industry. Scan test in combination with automatic test pattern generation (ATPG) for stuck-at and test have been the industry standard for many years. Scan based ATPG for structural at-speed test, or delay test, is also well known for about 20 years based on the gate delay fault model path delay fault model and transition fault model Many publications show that at-speed test is able to detect production defects that are not covered by static tests, Functional at-speed tests require a significant effort to develop compared to delay tests that are automatically generated by ATPG tools. Moreover, delay tests have a known fault coverage because of the usage of ATPG tools. Fault grading is difficult to impossible for functional atspeed tests. Thus, the fault coverage for functional at-speed tests usually remains unknown. Even though the advantages are multifold and well known, delay test is still far from being as popular as stuck-at fault test is for SOC (system-on-a-chip) devices. This is due to several challenges that must be addressed for delay test to be implemented as part of the overall production test strategy. The first observation is that the number of patterns needed to achieve a high fault coverage for transition fault testing is several times larger than the corresponding stuck-at pattern count. This implies, of course, the Xijiang Lin, Ron Press Mentor Graphics Corporation 8005 S.W. Boeckman Road Wilsonville, OR 97070, US same increase in production test time and in vector memory usage on automatic test equipment (ATE). In addition, the transition fault coverage is usually noticeably lower than the corresponding stuck-at fault coverage, For path delay testing, a small subset of structural paths is typically selected to be targeted by an ATPG tool. Thus, path delay fault coverage has only a very limited meaning with respect to the overall chip area. Besides the issues with fault coverage and pattern count, special design measures are required to run atspeed tests for several hundred designs on ATE with significantly lower speed capabilities. If high frequencies are generated on-chip for delay testing, then the ATPG tools need the ability to control the clock generation mechanism for all clock domains. In addition, the at-speed test data needs to be synchronized to the external low-speed tester. Looking at the still incomplete and growing list of issues, it is fortunate that solutions have improved over time and are continuing to improve. With the latest developments in the area of pattern compression, the impact of increased pattern count is significantly reduced

As design rules for delay test are better understood and ATPG tools become more and more mature to solve complex testability problems, fault coverage is also increasing. Design engineers select paths for path delay test more carefully in a manner that test results can be better correlated to production problems. Path delay tests can even be used for speed grading Several high frequency designs, that are tested speed with a low frequency ATE, have been reported over the past few years. High-speed clock signals are generated on-chip using the internal functional PLL. Examples for high-speed clock generation, but no implementation details, can be found in and With this approach, test data is synchronized to the external low-speed tester using a two-clock source strategy. Scan test data is using a slow clock signal generated by the ATE. The required at-speed delay test pulses are generated chip by the PLL. This paper presents a delay test concept for SOC devices with multiple clock domains. Circuitry for high-speed on-chip clock generation, implemented to avoid expensive test equipment, is described in detail. To the authors' knowledge, this is the first publication that presents implementation details for high-speed on-chip test clock generation. Enhancements to the presented clock generation circuitry, that are meant to improve fault coverage and pattern count, are discussed. Experimental ATPG results prove that the capabilities of the chip clock generation circuitry have an impact on achievable fault coverage and pattern count. The paper is organized as follows. The next section explains delay test fundamentals for SOC designs. Section three addresses implementation details of the on-chip clock generation circuitry. The fourth section discusses the delay test generation tasks from the ATPG tool perspective. Section five describes the experiments and the results achieved, respectively. Conclusions and an outlook are presented at the end of the paper.

Delay Test for State-of-the-Art SOC devices

Delay test is a two-vector (cycle) test. The first vector initializes the test. The second vector launches the desired transition at the source of a path under test and propagates the launched transition to an observation point. Test responses are captured with the next active clock edge at the observation point. Thus, test frequency requirements between initial and launch vector are relaxed, while the clock between launch and capture has to be operated at the functional speed of the device under test (DUT). Two techniques are known to apply two-vector tests using a standard scan architecture, "Scan shifting" or shifts the initial vector into the scan chains and generates the launch vector by using the last shifting cycle. In justification", "broadside or capture" the initial vector is shifted into the scan chains. The launch vector is the functional response of the DUT to the initial vector. "Scan shifting" requires the ability to switch the scan-enable signal at-speed. In addition, the risk of testing nonfunctional paths is higher for "scan shifting" since both vectors are completely independent of the DUT function. Due to the disadvantages of "scan shifting", it was decided to implement delay testing based on "jiunctionaljustification". The remainder of the paper refers to this delay test technique, SOC devices implement multiple functional clock domains. An at-speed test has to test all clock domains at their own functional speeds. Testing one clock domain after another is a potential solution for multi-clock domain delay test. However, the logic between the clock domains remains untested and the number of patterns is comparably high. Testing all clock domains simultaneously requires separate clock pins for each domain and a complex clocking procedure if an ATE is used to apply the test clock As already explained in the introduction, the usage of an ATE for clocking also requires a high speed clock generator to apply at-speed clock pulses for launch and capture. A high-speed clock generator is usually not available in low-cost ATE. Even if a high-speed clock generator is available, it is doubtful that a high-speed clock can be transmitted into the DUT. Today's especially controller devices, communicate to their environment at a comparably low speed. Therefore, the device pads are slow compared to the internal frequency. The application of an external high-speed clock would require the additional implementation of a high-speed pad that is capable of transmitting the clock signal. To overcome these issues the functional on-chip PLL can be used to generate at-speed clock pulses for test purposes. This delay is compensated during clock-tree balancing. It has therefore no impact on the chip timing.

There is no need for a high-speed relation between scan-clk and scan-en. After the test data is shifted into the scan chains, scan-clk is stopped and scan-en is set to with relaxed timing. Once scan-en is stable, scan-clk is clocked one time to trigger the enable mechanism that releases the two high-speed launch and capture clock pulses. scan-en is asserted and scan-clk operation is continued after the device is stable again. There is no need to synchronize the internal PLL clock to scan-clk or scan-en. The technique requires, of course, that a PLL clock signal is permanently available during the entire delay test. Besides the advantages already mentioned, the implementation is also testing the entire functional clock generation circuitry during delay test. Only scan shifting is performed with relaxed speed. Furthermore, since the scan chains are not used in functional mode there is no need to test them speed.

Delay Test ATPG

Delay test ATPG has to consider at least two consecutive clock cycles, as delay test is a vector test. Due to the sequential nature of the ATPG problem, delay test ATPG is more complex than stuck-at ATPG. The use of more than one clock cycle during ATPG is already known for stuck-at ATPG. Additional clock cycles are used to initialize sequential elements such as non-scan cells and known as "clock sequential" and "RAM sequential ATPG, respectively. This adds even more complexity to the delay fault ATPG problem. But especially access to is important for delay testing as critical functional timing paths frequently involve functional paths from and to Delay test is an at-speed test in which all clock domains could run at their functional speeds simultaneously if tested in parallel. To prevent wrong capture values for signals passing between clock domain boundaries, it is important that the ATPG tool is able to understand complex clocking schemes If at-speed clock pulses are generated by an on-chip PLL, then the ATPG tool must be able to control the on-chip clock generation. If the CPF from Figure 3 is used, clock generation is controlled by scan-en and scan-clk only. To generate "clock sequential" and "RAMsequential" patterns an enhanced CPF as well as a more advanced control mechanism is required. This is not an issue when an external clock is used since the ATPG tool can decide how many clock cycles need to be applied. To get the same freedom with on-chip clock generation, a dedicated control protocol to setup the PLL from the ATPG tool is required. The efficiency of an ATPG tool is significantly reduced if every cycle into and through the PLL CPF needs to be simulated. Six or more pulses during functional mode may be required to produce a desired clock pulse pair at Therefore, procedures referred to as named capture procedures were developed. This number is identical to the stuck-at fault count as both fault models are targeting two faults at each gate terminal. However, it is important to note that not all fault sites that are testable for stuck-at faults are also testable for delay faults.

Experimental Setup

For all experiments, but (a), the transition fault coverage and pattern count was determined.

Experimental Results

Test generation results for both the stuck-at faults and the transition faults are shown in Table 1. Experiment (e) again uses a common external clock for both clock domains. This experiment is used to determine the coverage that would be achievable for a most flexible CPF. It also excludes any effects that might be caused by the interaction of the two clock Table 1:Experimental Results domains or limitations of the ATPG tool dealing with on-chip clock generation. The reached coverage is still 6.6% lower than the reference value of experiment (b). Since the only differences between experiments (b) and (e) are the constraints added to make the test applicable at the ATE, these limitations and restrictions must be the reason for the coverage reduction. The pattern count for experiment is nearly five times higher than the stuck-at pattern count. Using on-chip clock generation, experiment (c) and (d), increases the pattern count again by more than a factor of two. Experiment (e) shows that an enhanced CPF reduces the pattern count by more than 15% compared to experiment (d).

6 Conclusions Even though delay defects become increasingly important for new technologies, high-speed testers are hardly affordable for SOC devices targeting consumer products. Therefore, high-speed on-chip clock generation for delay testing is one cornerstone of SOC test strategies. For the device under investigation the transition test coverage is reduced by more than 7% when simple two-pulse on-chip clock generation is implemented. Moreover, increased pattern count requires a more extensive use of an on-chip technique to reduce scan chain length. Only using this technique the observed pattern count can be loaded into the ATE vector memory without truncation of the test pattern set. Experiments have shown that enhancements in onchip clock generation capabilities improve the test coverage and reduce the pattern count. To achieve further improvements work will focus on two main objectives. ATPG development will concentrate on enhanced fault classification and fault grouping. Many faults included in the transition fault coverage report are actually faults and will make the coverage appear lower than the actual quality of the test. An attempt will be made to classify and group these faults as non-functional scan path, low-speed and other faults that cannot cause the device to fail at-speed operation.

Fig. 2 :

 2 Fig. : Device with clock pulse filters (CPF) for each of the two clock domains

  Named capture procedures provide a simple behavioral model of the clock generation logic. The model describes the behavior of the output clock signal (elk-out) in response to primary input signals (scan-en, scan-clk). As a result, the named capture procedures can model internal clock generation logic as a couple of internal clock pulses during ATPG. When the patterns are saved for ATE, the internal clock pulses are converted to the corresponding primary input signals that will produce them. An additional consideration when creating delay patterns is that the device usually cannot perform at the high frequencies of the PLL clocking. In addition, it is difficult at the ATE to reference the external timing to an on-chip generated clock. Therefore, any inputs driven by the ATE or output pin responses must not require speed timing in relation to the clocks or other signals. As a result, it is normally necessary to mask outputs from being observed and to ensure that primary inputs only change well ahead of the launch clock pulse. Named capture procedures support this by only forcing inputs and measuring outputs when they are explicitly specified. Utilizing CPF logic for delay testing can be used for transition fault model and path delay fault model patterns. It can also be extended to provide clocking when applying memory tests through the scan logic. This technique is sometimes referred to as macro testing and enables at-speed testing of memory operations without adding any memory test logic 5 To determine the impact of on-chip clock generation on fault coverage and pattern count, ATPG experiments based on the transition fault model were performed. The path delay fault model was not used for comparison since the path delay fault coverage is highly dependent on the testability of the preselected paths. ATPG settings are compatible throughout all experiments to ensure comparability of results. Experiments were done using the of a technology micro-controller SOC device with a total logic gate count of Two synchronous functional clock domains operate the device, running at 75 and 150 357 balanced internal scan chains, based on an EDT architecture, with 36 external scan channels, are implemented for multiplexed scan cells. The number of collapsed faults considered is

  (a) Stuck-at test using single external clock: Both clock domains are operated by a common external scan clock. RAM sequential pattern are not considered to allow identical ATPG settings for all experiments. (b) Transition test using single external clock: Same setup as in (a). This experiment reveals the maximum achievable transition fault coverage if the device would consist of a single clock domain. The scan clock and are controllable and observable from the ATE. (c) Transition test using on-chip clock generation: For each of the two functional clock domains a CPF block as shown in Figure 3 is used, providing two clock pulses. Additional constraints required for the on-chip clock generation and ATE execution are added (no launch or capture using test controller clock or system reset, scan enable always inactive during capture phase, not used, feedback paths through bidirectional pads not utilized). (d) Enhanced CPF block to generate up to 4 highspeed clock pulses and inter-domain test: The same experiment as in (c), but the CPF blocks are enhanced and able to provide two, three or four clock pulses. In addition, the CPF blocks provide the capability to generate tests for domain signals crossing the boundaries of the synchronous clock domains. These tests apply a launch pulse in one clock domain and a capture pulse in the other clock domain. (e) Single external clock with constraints and masking: This experiment gives the coverage that would be reachable by the most flexible CPF blocks possible. Instead of the two CPF blocks, a single external clock is used as in experiment (b). All other constraints required by an internal clock generation are still taken into account as introduced in experiment (c).

  Column depicts the test coverage achieved in percentage while column Pattern" gives the associated pattern count. Tool runtimes are not reported because experiments were run on different type of Tool runtimes were in the range of one day for stuck-at faults and about one week for transition faults. The test coverage reaches 98.7% for stuck-at faults. The remaining stuck-at faults are, 1% ATPG untestable, 0.3% aborted. The ATPG efficiency for transition fault experiments (b), (c), and (d) is also above 99%. For experiment (e) the ATPG is 97.7%. Comparing results (a) and the coverage for transition faults is already 3.7% lower than the stuckat fault coverage, even if multiple clock domains and high-speed on-chip clock generation are not considered. Experiment (c) shows that the coverage for a real applicable transition test using on-chip clock generation is much lower compared to the reference value of experiment (b). Main reason for the coverage drop are additional test generation constraints required to enable the use of CPF blocks as described in Figure 3. Moreover, external clock generation allows multiple pulses to initialize nonscan cells and while only exactly two clock pulses are generated by the internal CPF block. Another difference experiment (b) is that both clock domains are tested with independent clocks and only one CPF block is used per scan load. Therefore, no inter-domain test is possible. To overcome the coverage reduction caused by the simple CPF used in experiment (c) a more flexible CPF is assumed in experiment (d). The new capabilities of the enhanced CPF also enable the generation of three or four clock pulses and allow the launch and capture between the different clock domains. The enhanced capabilities of the CPF increase the coverage by 0.6%.

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

Circuit development will concentrate on further analysis of root causes for design related coverage reduction. For those faults not tested but relevant for product quality, counter measures need to be developed to achieve an acceptable coverage. For example, at-speed testing of logic between clock domains has been avoided in the past. The experiments show that these tests, that are meaningful for signals between synchronous clock domains, improve the coverage at least to some extent.

In the future it needs also to be proven that enhanced delay tests guarantee the same quality level as today's functional at-speed tests. pp. [459][460][461][462][463][464]1997


Minh Ôn

Vũ Ngo

Jonathan Fabrizio

Thierry Géraud

SALIENCY-BASED DETECTION OF IDENTITY DOCUMENTS CAPTURED BY SMARTPHONES

Keywords: Document detection, Visual saliency, Identity document, Mathematical morphology, Smartphonebased acquisition

Smartphones have became an easy and convenient mean to acquire documents. In this paper, we focus on the automatic segmentation of identity documents in smartphone photos or videos using visual saliency (VS). VS-based approaches, which pertain to computer vision, have not be considered yet for this particular task. Here we compare different VS methods, and we propose a new VS scheme, based on a recent distance belonging to the scope of mathematical morphology. We show that our resulting saliency maps are competitive with state-of-the-art visual saliency methods, and that such approaches are very promising for use in identity document detection and segmentation, even without taking into account any prior knowledge about document contents. In particular they can perform in real-time on smartphones.

INTRODUCTION

Smartphones are able to easily capture images and take videos; thanks to this convenience, many users use smartphones as a tool to acquire documents instead of a traditional scanner. In this paper, we focus on the detection of identity documents, such as visas, passports, and identity cards, in photos or videos acquired by a smartphone. This detection task can be actually seen as the segmentation of the image into two parts: the document and the background-note that the term "document segmentation" usually refers to the segmentation of the document contents into several parts. Knowing the precise area of the document allows to guide the user during the image acquisition, to check for forgeries, to properly archive the document, and also to identify the model of document [START_REF] De Las Heras | Use case visual bag-of-words techniques for camera based identity document classification[END_REF][START_REF] Sicre | Identity documents classification as an image classification problem[END_REF]. There are many difficulties in such a real-world mobile-based application: the scene background is unknown; lighting conditions are highly variable (with poor contrast, and unreliable color tones); illumination defects can appear (inhomogeneity, shadows, specular reflections); last, some problems due to the acquisition can occur (out-of-focus blur, motion blur, optical distortions, and noise). In this paper, we assume that the type of identity document present in an image to process is unknown. Typically, we consider situations where we can have passports from different countries, such as in an airport. That implies that docu-ments can have different kinds of contents (layout, text zones, pictures, background). As said before, we want to delineate precisely the document boundary, so its contents (presence of a face photo or of text) is actually of poor help.

To detect documents, the most classical approach is to extract lines from contours as candidates for being a document side [START_REF] Burie | ICDAR 2015 competition on smartphone document capture and OCR (SmartDoc)[END_REF] (see also [START_REF] Liang | Camera-based analysis of text and documents: A survey[END_REF], which presents a survey on camera-based analysis of documents, and the recent paper [START_REF] Bulatov | Smart IDReader: Document recognition[END_REF]). Here we put aside theses approaches, since we are going to explore a radically different approach, the visual saliency-based one. That is why Sec. 2 only focuses on salient object detection 1 . Many salient object detection methods, for use in computer vision, have been recently defined using the Minimum Barrier Distance (MBD) [START_REF] Strand | The minimum barrier distance[END_REF], the first ones being [START_REF] Zhang | Minimum barrier salient object detection at 80 fps[END_REF][START_REF] Tu | Real-time salient object detection with a minimum spanning tree[END_REF], and the most recent one being [START_REF] Huang | Water flow driven salient object detection at 180 fps[END_REF]. This particular distance and a distance which derives from it [START_REF] Géraud | Introducing the Dahu pseudo-distance[END_REF], whose computation is very fast, are detailed in Sec. 2. That latter distance is the cornerstone of the method that we present in Sec. 3 to detect documents. This method computes a saliency map, that is, an intensity image where the pixels of salient objects are brighter than the other pixels. Then we binarize this map to obtain the final segmentation result.

The two main contributions of this paper are: 1. an extension to color images (Sec. 3.2) of the Dahu distance, originally defined on gray-level images [START_REF] Géraud | Introducing the Dahu pseudo-distance[END_REF], which allows for computing saliency maps, 2. and a study (Sec. 4) that compares different saliency-based methods for the segmentation / detection of identity documents.

SALIENT DOCUMENT DETECTION

This section describes the saliency map we will use in the document segmentation method presented in Sec. 3.

Saliency based on the Minimum Barrier Distance

The Minimum Barrier Distance (MBD) has been defined in the seminal paper [START_REF] Strand | The minimum barrier distance[END_REF], and later studied in [START_REF] Ciesielski | Efficient algorithm for finding the exact minimum barrier distance[END_REF][START_REF] Strand | The minimum barrier distance: A summary of recent advances[END_REF]. Considering that the image domain is a graph, where vertices repre- (d) u as a surface. sent the discrete points of the domain, we can define paths on this graph. A gray-level image (such as in Fig. 1(a)) is then a vertex-valued graph (such as in Fig. 1(b)). The barrier τ of a path π = ..., π i , ... (π i being a vertex of the graph) in a gray-level image u is defined by:

0 0 0 1 3 2 1 [1,3] 1 3 2 2 0 0 0 0 0 0 0 0 0 0 0 1 2 [1,3] [2,3] [2,3] [0,3] [0,3] [0,3] [0,2] [0,2] [0,1] [0,1] { } { } { } { } { } { } { } { } { } { } { } { } { } { } { } { } { } { } { } { } { } { } { } { } (e) Interval-valued image u. 0 0 0 1 3 2 1 1 1 1 3 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 2 2 2 1 2 3 1 3 (f) A minimal path in a u < -u.
τ u (π) = max πi∈π u(π i ) -min πi∈π u(π i ). (1)
The barrier thus represents the gray-level dynamics in u along a path. The minimum barrier distance between x and x ′ in u is then defined by:

d MB u (x, x ′ ) = min π∈Π(x, x ′ ) τ u (π), (2)
where Π(x, x ′ ) denotes the set of all paths between two vertices x and x ′ . The minimum barrier distance is thus the minimum gray-level dynamics that we can have along a path between two vertices. A simple illustration is given in Fig. 1. In the graph-based representation depicted in Fig. 1(b), between the two red vertices, multiple paths are possible. The path π corresponding to the sequence of values 1, 3, 0, 0, 2 is such as τ u (π) = 3-0 = 3; it is not minimal since we can have paths with a lower barrier value. A minimal path w.r.t. the MBD is depicted in blue, and we have d MB u (x, x ′ ) = 2. From a distance, we can derive a saliency map, that is, an image where the image value at a point x is the distance of x to a given set of points X ′ ; formally:

S MBD u (x, X ′ ) = min x ′ ∈X ′ d MB u (x, x ′ ). (3)
The computation of a saliency map using the exact MBD is costly [START_REF] Ciesielski | Efficient algorithm for finding the exact minimum barrier distance[END_REF]; yet some fast but approximate algorithms exist, based on the minimum spanning tree of the image [START_REF] Tu | Real-time salient object detection with a minimum spanning tree[END_REF]. The next section presents a variant of the MBD, which is also based on the notion of barrier (Eq. ( 1)), and which leads to an exact and efficient computation of saliency maps.

The Dahu Distance and the Tree of Shapes

In [START_REF] Géraud | Introducing the Dahu pseudo-distance[END_REF], a "continuous" version of the MBD has been defined, where a gray-level image is interpreted as a surface. An illustration is given in Fig. 1(d) for the image in Fig. 1(a). We can define paths on this surface, and a minimal path is depicted in blue in Fig. 1(d), having a barrier of 1 gray-level. This continuous representation of images thus leads to a slightly different distance. Let us now recall briefly how the continuous version of the MBD is defined in [START_REF] Géraud | Introducing the Dahu pseudo-distance[END_REF].

A gray-level image can be seen as a function u : Z 2 → N, but such a function is inappropriate to represent a surface such as the one in Fig. 1(d). In [START_REF] Géraud | Introducing the Dahu pseudo-distance[END_REF] the authors have proposed to replace the domain Z 2 by the topological space H 2 of 2D cubical complexes, and the co-domain N by the set I N of intervals on natural numbers. Briefly put, a 2D cubical complex is a set of elements that have a geometrical interpretation: it is composed of squares (2D elements), of segments (1D elements), and of points (0D elements). Fig. 1(e) depicts these elements, where segments and points are respectively drawn as rectangles and tiny squares. The 2D elements correspond to the original pixels of the image (in salmon pink in Fig. 1(e)), whereas the other elements correspond to "what lies between the pixels". From a scalar-valued image u we construct an interval-valued image u which really represents the surface corresponding to u.

For instance, the scalar image u in Fig. 1(a) can be seen as the surface depicted in Fig. 1(d). The corresponding intervalvalued image u depicted in Fig. 1(e), and in 3D in Fig. 1(c), is a way to represent this surface. Actually, the 0D and 1D elements of the complex which have non-degenerated interval values (in yellow in Fig. 1(e)) encode the vertical parts of the surface. For instance, the 1D element e with the purple border in Fig. 1(e) is such as u(e) = [START_REF] Sicre | Identity documents classification as an image classification problem[END_REF][START_REF] Burie | ICDAR 2015 competition on smartphone document capture and OCR (SmartDoc)[END_REF]; it represents the vertical part of the image surface depicted in purple both in Fig. 1(c) and in Fig. 1(d).

Let us denote by <the relation between a scalar image and an interval-valued image stating that the values of the pixels of the former are "included" in the interval values of the pixels of the latter; formally: u < -u ⇔ ∀ x, u(x) ∈ u(x). Fig. 1(f) depicts a scalar image u which is "included" in the interval-valued image u depicted in Fig. 1(e). The adaptation of the minimum barrier distance to an interval-valued image / function, called the Dahu distance [START_REF] Géraud | Introducing the Dahu pseudo-distance[END_REF], is the following:

d DAHU u (x, x ′ ) = min u < -u d MB u (h x , h x ′ ) (4) = min u < -u min π∈Π(hx, h x ′ ) τ u (π), (5)
where h x and h x ′ are the 2D elements of the complex corresponding to x and x ′ . Fig. 1(f) depicts in blue a minimal path w.r.t. the Dahu distance; it is obtained with a particular scalar image included in the interval-valued image u depicted in Fig. 1(e). This minimal path corresponds to the one depicted on the surface of u in Fig. 1(d), and gives a distance of 1 graylevel between the two red pixels.

As compared to the minimum barrier distance (see Eq. ( 2)) there is an extra combinatorial layer with the minimization "min u < -u ". Yet, this new distance can be very easily and efficiently computed thanks to a tree-based representation of the image. The tree of shapes [START_REF] Monasse | Fast computation of a contrastinvariant image representation[END_REF][START_REF] Caselles | Geometric Description of Images as Topographic Maps, ser[END_REF] is a morphological decomposition of gray-level images into connected components, called shapes, which can be arranged into a tree; indeed, two shapes are either disjoint or nested. Quickly said, a shape is the interior of an iso-level line. In Fig. 2, an illustration of a tree of shapes is given and, for instance, the sub-tree B ∪ D ∪ E corresponds to a shape, the contour of which being a dark-gray iso-level line. In Fig. 2(a), the blue path between the two points (x, x ′ ) indicated by red bullets in u starts from region B, then goes through A and C, and finally ends in region F. Such a path is minimal because every path in Π(x, x ′ ) should at least cross this same set of level lines to go from x to x ′ ; thus the Dahu distance corresponds to the level dynamics of this set of lines. Actually this path in the image space is exactly the path on the tree of shapes between the nodes t x and t x ′ containing respectively the two red endpoints x and x ′ ; see the blue path on the tree depicted in Fig. 2(c). In the following, a path on a tree is denoted by

• π (to distinguish it from paths in the image space).

The Dahu distance between x and x ′ can therefore be reexpressed directly on the tree of shapes S(u) of u as being the minimum barrier distance between the nodes t x and t x ′ :

d DAHU u (x, x ′ ) = d MB S(u) (t x , t x ′ ) = max t ∈ • π(tx, t x ′ ) µ u (t) - min t ∈ • π(tx, t x ′ ) µ u (t), (6)
where µ u (t) denotes the gray-level associated with the node t of S(u). For instance, in Fig. 2(c), the blue path gives the sequence of node values 0, 1, 2, 1 , so the Dahu distance is 2-0 = 2. Eventually, there is no need to find the best scalar image u < -u, nor the best path π ∈ Π(x, x ′ ) in the image space; it thus means that the primary definition of the Dahu distance (Eq. ( 5)) is not used as is. The new expression of the distance (Eq. ( 6)) is just a barrier computation (such as Eq. ( 1)), but on the trivial path • π(t x , t x ′ ) of nodes of the tree of shapes.

Saliency based on the Dahu Distance

A saliency map of an image u can be derived from this new distance, such as in Eq. ( 3), except that this new saliency map has a direct expression on the tree of shapes S(u). With a set of points X ′ , the corresponding set of nodes on S(u) is:

T X ′ = { t x ′ ; x ′ ∈ X ′ } ⊂ S(u). (7)
The saliency map from X ′ based on the Dahu distance can then be expressed by:

S DAHU u (x, X ′ ) = min x ′ ∈X ′ d DAHU u (x, x ′ ) = S MBD S(u) (t x , T X ′ ). ( 8
)
The major difference with a classical saliency map, defined in the image space (such as the one of Eq. ( 3)), is that the tree structure is one-dimensional. Since the Dahu distance on the tree (given by Eq. ( 6)) has the form of a barrier "max -min", the saliency map S MBD S(u) expressed on the tree can be computed by a two-pass procedure (here, downwards then upwards) like the very classical computation of a chamfer distance map [START_REF] Borgefors | Distance transformations in arbitrary dimensions[END_REF]. Afterward, getting the 2D saliency map S DAHU u means reading for each x the value of S MBD S(u) at t x . Eventually, once computed the tree of shapes S(u), the computation of a saliency map x → S DAHU u (x, X ′ ) is instantaneous, whatever the set X ′ . Last, let us mention that the representation of an image into a tree of connected components is not memory consuming and is very easy to manipulate [START_REF] Carlinet | A comparative review of component tree computation algorithms[END_REF]. The tree of shapes of an image can be computed in quasi-linear time complexity w.r.t. the number of image pixels [START_REF] Géraud | A quasilinear algorithm to compute the tree of shapes of n-D images[END_REF], and can be parallelized [START_REF] Crozet | A first parallel algorithm to compute the morphological tree of shapes of nD images[END_REF].

PROPOSED METHOD

We now present a method that relies on saliency maps based on the Dahu distance (Eq. ( 8)) to detect identity documents.

Overview of the Method

The method we propose is composed of four steps. 1. We rely on the SLIC algorithm [START_REF] Achanta | SLIC superpixels compared to state-of-theart superpixel methods[END_REF] to simplify the image into superpixels (clusters of pixels, i.e., very tiny regions). This step is interesting because it removes unnecessary image details, and the image can now been seen as a graph of superpixels, which has a reasonable size (instead of a huge matrix of pixels). That drastically reduce the number of elements to deal with for the next steps. 2. To each superpixel we assign its average color, and a tree of shapes is computed from this graph. 3. We then produce a saliency map from this structure, and we normalize this map (Sec. 3.3). 4. Finally, we apply a detection step to obtain the resulting detection (Sec. 3.4).

Let us remark that steps 2 and 3 require to compute respectively the tree of shapes and Dahu distances on a color-valued graph; yet both this tree and this distance are originally defined on scalar data (gray-valued images and graphs). So, before giving the method details, we first have to extend these notions to color data.

Extension to Color Data

The tree of shapes, primarily defined on gray-level images, has been recently extended to multi-valued data [START_REF] Carlinet | MToS: A tree of shapes for multivariate images[END_REF]; this extension is called the Multivariate Tree of Shapes (MToS). It yields that we can represent color images by a tree mapping the inclusion of shapes, that is, connected components without holes. Such a representation is of prime importance for computer vision [START_REF] Cao | A Theory of Shape Identification[END_REF] because it satisfies some strong invariance properties featured by natural images, such as local contrast changes [START_REF] Caselles | Topographic maps and local contrast changes in natural images[END_REF].

However, the definition of the Dahu distance on the tree of shapes Eq. ( 6) cannot be used as is; it shall be adapted to take into account that we have color data. Let us now consider that u is a color image, t is a node of the MToS of u, and µ u (t) is the color associated with node t. A superscript i is used to stand for taking one component of the color given by µ. We can then re-write the Dahu distance as follows:

with Fig. 3. Effect of fusing four side-specific maps using Eq. ( 11).

τ (i) u ( • π) = max t∈ • π µ (i) u (t) -min t∈ • π µ (i) u (t), (9)
d DAHU u (x, x ′ ) = i∈{R,G,B} τ (i) u ( • π(t x , t x ′ ) ). (10)
This distance is therefore the sum of the lengths of the 3 sides of the minimum 3D bounding box of the set of colors corresponding to the nodes along the path between t x and t x ′ . This modified Dahu distance can now be used to compute the saliency map of Eq. ( 8). 2

Obtaining a Relevant Saliency Map

We assume that the four sides of the image boundary are mostly composed of the scene background (i.e., the document does not predominantly touch the image boundary). Hence, from each boundary side of the image, we compute a saliency map; for instance, with X top being the set of pixels of the image top row, we have the saliency map S DAHU u (x, X top ). We end up with 4 saliency maps, depicted in Fig. 3(b), that we combine in a pixel-wise way using:

S DAHU u (x) = i∈{top, left, right, bottom} S DAHU u (x, X i ) / 4. ( 11
)
An example is given in Fig. 3. As we can see in Fig. 3(a), the fact that the document touches the top row gives an irrelevant saliency map S DAHU u (x, X top ), marked T in Fig. 3(b). However, after the fusion of the 4 maps, we obtain a satisfy result, which is depicted in Fig. 3(c).

Similarly to some previous works [START_REF] Wang | High-level background prior based salient object detection[END_REF][START_REF] Ciesielski | Efficient algorithm for finding the exact minimum barrier distance[END_REF][START_REF] Strand | The minimum barrier distance: A summary of recent advances[END_REF], we normalize the saliency map by using "a -b" normalization (with a = 0.1 and b = 0.8), followed by an adaptive contrast enhancement with a sigmoid mapping. The saliency map in Fig. 3(c) is depicted after normalization in the 2nd row of Fig. 5(f).

Final Detection Step

The final detection step consists in deducing a binary image from the saliency map obtained by Eq. [START_REF] Ciesielski | Efficient algorithm for finding the exact minimum barrier distance[END_REF]. Our detection step is still experimental (briefly put, we only search for a threshold so that the result looks like a quadrilateral); it is not emphasized in this paper, since we focus on comparing gray-level saliency maps w.r.t. all possible thresholds in Sec. 4.2. Though, with this simple detection step, some preliminary results are depicted in Fig. 5(g) with the following color code: white for true positives, red for false negatives, and green for false positives. 2 Please note that, although Eq. ( 10) looks simple, we have here a strong result. To be able to compute visual saliency maps (efficiently, and based on the very effective Minimum Barrier Distance) while taking into account colors, we need to compute a particular distance between two points. This distance is the one of an optimal path between two points in the image space, this path being such that the set of colors on the path has the smallest bounding box in the color space. Precisely, the distance between the 2 points is the diameter (with the L 1 norm) of this 3D bounding box. This is a highly combinatorial problem, far to be trivial, and which cannot be solved efficiently in the image space. Our contribution here is to turn this problem into an efficient straightforward computation in a tree space.

EXPERIMENTAL RESULTS

To know how our Dahu-distance-based saliency method performs in the context of identity document segmentation, we are going to compare it with some other similar approaches.

Some Other Saliency Detection Methods

Let us now present three state-of-the-art methods of salient object detection, that we are going to compare our method with.

In [START_REF] Wei | Geodesic saliency using background priors[END_REF] the saliency detection is based on a geodesic distance (GS) which uses background priors. The major assumptions are that the background is usually large, homogeneous, and located near the boundary of the image. In [START_REF] Yang | Saliency detection via graph-based manifold ranking[END_REF] the saliency detection relies on a bottom-up approach to choose some regions by manifold ranking (MR) on a graph of superpixels. Such as in Sec. 3.3, the authors compute 4 maps and fuse them. In these maps, the superpixels are ranked w.r.t. the similarity with some seeds located in the image boundaries. In [START_REF] Zhu | Saliency optimization from robust background detection[END_REF], a saliency optimization method (SO) is proposed which combines multiple saliency measures, one of them using the notion of "boundary connectivity". Note that all these methods also rely on a postprocessing step to "normalize" the resulting saliency maps.

Dataset and Experiments

For our experiments, we have built a dataset of identity documents 3 . We have a dozen of different types of visas and passports from various countries. We recorded over 100 videos under different environment conditions, using several kinds of smartphones. From these videos, we selected 100 frames to create our dataset, so that it presents some realistic difficulties such as out-of-focus and motion blur, inhomogeneous illuminations, etc. Then, we generated semi-automatically the corresponding ground-truth images. We compare our method with the state-of-the-art saliencybased detection methods presented in the previous section. We use two distinct measures: 1. the Mean Absolute Error (MAE), which is the average difference between a saliency map S (gray-level image) and a ground-truth image GT (binary image): MAE = ( x |GT (x) -S(x)|) / N, with N being the number of pixels, and 2. an F β -measure defined by: F β = (1 + β 2 ) × P × R / (β 2 × P + R), where P and R are respectively the precision and the recall, and with β 2 = 0.3 (it is the classical setting in the visual saliency community).

To compute the precision and recall scores, for each image to process, we simply binarize the corresponding gray-level saliency map with a threshold sliding from 0 to 255. Then, for every threshold, we compare the obtained binary map with the ground-truth map. For a given threshold, we depict in Fig. 4(b) the average F β -measure obtained on the dataset of 100 images.

The "global" F β -measure, averaged for all thresholds (and all images), is denoted by F β . The values of F β and the MAE scores for all the compared methods are depicted in the table in Fig. 4(a); note that the better a method is, the lower MAE values are, and the higher F β values are. First, we can observe that, over the years, the state-of-the-art methods give better results (first GS, then MR, and last SO). Second, the Dahu-based approach gives the lowest MAE score, and slightly outperforms the SO method for the F β criterion.

If we look at the F β -measure curves for the different thresholds in Fig. 4(b), there are two main observations. First, the methods SO (in gray) and Dahu (in red) have stables / flat curves, which is an advantage, because the "best" threshold remains unknown and depends on the image. Conversely, for the GS and MR methods (respectively in blue and green), the curves are not stable, which means that taking a threshold might not be a very robust task. The second observation is that the "best" method with respect to the F β -measure seems to be the MR method, with a rather low threshold (around 50). Though, the MR method is computationally expensive so it cannot run in real-time on smartphones, whereas the Dahu-based approach can. Some qualitative illustrations on a few images (Fig. 5(a)) are depicted in Fig. 5. The prominent observation is that the compared saliency methods, from Fig. 5(b) to Fig. 5(f), have rather different behaviors. The one based on the Dahu distance, so on the principle of a barrier (see Eq. (1), Eq. ( 6), and Eq. ( 9)) is effective: the main barrier is visible around the documents, even before normalization; see Fig. 5(e). Also we can notice that the saliency values inside the documents are much more uniform with the Dahu-based method than with the other saliency-based methods.

Limitations and Perspectives

The major limitation of saliency-based methods is due to low contrast; some failure cases are depicted in Fig. 5(i). The left image is blurred and the contrast between the document and the background is poor, so the document cannot be detected. In the right image, the identity card has a color similar to the one of the background, so the salient objects are the hand and the portrait. Actually, as perspectives, the method we present can be improved through taking into account some extra prior information such as "text texture", and can be combined with more classical contour/line-based approaches.

RELATED WORK

Actually, there exists a short state of the art of document detection, contrasting from methods to extract lines as candidates for the document sides, and being related to the one presented here. In [START_REF] Leal | Smartphone camera document detection via Geodesic Object Proposals[END_REF], after down-sampling, some seeds are located in the image, and the "geodesic object proposals" method [START_REF] Krähenbühl | Geodesic object proposals[END_REF] extracts from these seeds a set of regions; the best candidate region is then elected as being the document. In [START_REF] Xu | Hierarchical image simplification and segmentation based on Mumford-Shah-salient level line selection[END_REF] and [START_REF] Xu | Hierarchical segmentation using tree-based shape spaces[END_REF], the authors proposed a method based on the tree of shapes [START_REF] Carlinet | MToS: A tree of shapes for multivariate images[END_REF]. For each shape (node of the tree / connected component without hole), an energy is computed being the sum two terms: one measuring how the shape fits a quadrilateral, and the other one measuring the degree of "text texture" of the contents of the shape. The shape with the highest energy is considered as the candidate for document detection. This approach won the first challenge (detection of a document page in videos captured by smartphones) of the SMARTDOC competition, organized for ICDAR 2015 by Burie et al. [START_REF] Burie | ICDAR 2015 competition on smartphone document capture and OCR (SmartDoc)[END_REF]. The work presented in this paper, relying on a saliency map computed on the tree of shapes, is clearly derived from it.

CONCLUSION AND PERSPECTIVES

In this paper, we have presented an extension of the Dahu distance to color images, which allows for computing some saliency maps for object detection purpose. We have proposed a framework to detect identity documents in photos or videos captured by smartphones based on saliency maps, with very few prior knowledges about the documents and the images. We only take into account that the document looks like a quadrilateral and does not mostly touch the image boundary. Our main conclusion (and contribution) is that visual saliency approaches are relevant to document detection. Moreover, while remaining efficient (both in time and memory usage), which is critical in embedded software, we have the potential to offer better results than the one presented here, using some extra knowledge. Indeed, finding some text [START_REF] Huỳnh | Morphology-based hierarchical representation with application to text segmentation in natural images[END_REF] or a face photograph can help the final decision step in locating the document, though that does not directly help delineating the document boundary. Last, we will also consider images acquired by tablets and webcams to test the robustness of the saliency approach.

  u as a graph.

  3D version of u given in (e).

Fig. 1 .

 1 Fig. 1. Image representations for computing barrier distances.

  Tree S(u).

Fig. 2 .

 2 Fig. 2. The tree of shapes of an image allows to easily express and compute the Dahu distance and saliency maps.

MethodFig. 4 .

 4 Fig. 4. Numerical comparison of saliency maps.

Fig. 5 .

 5 Fig. 5. Comparison of our saliency maps with other classical or state-of-the-art methods.

† This work has been conducted in the context of the MOBIDEM project, part of the "Systematic Paris-Region" and "Images & Network" Clusters (France). This project is partially funded by the French Government and its economic development agencies.[START_REF] De Las Heras | Use case visual bag-of-words techniques for camera based identity document classification[END_REF] It also explains that a comparison between saliency-based methods and some more classical line/contour-based methods is left as future work. Our intent here is only to see whether using saliency can be effective to document detection and segmentation.

Available at http://publications.lrde.epita.fr/movn.18.das

Acknowledgments. The authors would like to thank Nicole Vincent and Jean-Christophe Burie for their valuable comments on a preliminary version of this work.


Fernando Rincon
email: fernando.rincon@uclm.es

Francisco Moya
email: francisco.moya@uclm.es

Jesus Barba
email: jesus.barba@uclm.es

Juan Carlos Lopez
email: juancarlos.lopez@uclm.es

Fernando Rincón

Jesús Barba

Juan Carlos López

Model Reuse through Hardware Design Patterns

come   L'archive ouverte pluridisciplinaire

Introduction

A significant increase in design productivity is usually a direct consequence of two key factors: 1) raising the abstraction level, and 2) reusing previous designs.

Design reuse is usually achieved using IP-based methodologies (hard, firm and soft IP [START_REF]Vsi alliance architecture document[END_REF]). IP blocks offer closed solutions and limited flexibility (parameterization or configuration). They are usually optimized under some assumptions and modifications are either impossible or extremely tricky, with the exception of some extensible IPs such as configurable processors which are designed with user modification in mind. Besides, in most cases these IP blocks are completely designed at the RT level using an HDL.

Most often system designers would like to reuse behavioural level abstractions (algorithms) while IPs usually just offer implementations of such algorithms under a certain set of constraints. The solutions proposed to this problem range from behavioural level modeling to high level synthesis. Unfortunately, these higher level tools may introduce large overheads in terms of resource allocation and performance of the final solution.

In this paper we propose a focus shift from componentlevel reuse as advocated by IP-based methodologies to model-level reuse as represented by current software engineering practice. Our point of view improves reusability at two levels: 1) at the system-level, using pattern oriented modeling. Most design patterns are not related to a particular implementation. 2) At the component-level, introducing a broader sense of genericity than the only currently available in HDLs, in order to allow generic algorithm descriptions.

There has been a lot of discussion on the technical problems of component-level reuse, the key goal of most IPbased methodologies. Some of these problems are still open to discussion: 1) integration of components in the design flow, 2) interface compatibility and generation, and 3) customization and optimization. The IP designer is faced with these issues very early in the system design cycle, with the risk of precluding reusability under unforeseen scenarios.

Published literature proposes partial solutions for each of the above mentioned issues: 1) IP-based methodologies ease the integration of third party IPs into the design flow, 2) interface compatibility is usually handled through standardization [START_REF]Vsi alliance architecture document[END_REF] and wrapper generation [START_REF] Damasevicius | Application of design patterns for hardware design[END_REF], and 3) behavioural IPs [START_REF] Pillement | Behavioral ip specification and integration framework for high-level design reuse[END_REF] and high-level synthesis provide the ability to adapt IPs to new scenarios.

Nevertheless, reusing a predefined component may be the source of area and performance overheads due to either interface compatibilization or unnecessary IP features. The latter is not uncommon since IP reusability is usually improved by considering several target scenarios. Modifications of third party IP are either impossible or extremely tricky. In this paper we propose model reuse in contrast to component reuse.

Most of current IPs are designed at the RT-level using a conventional hardware description language. Raising the level of abstraction would provide two important benefits: 1) models would be easier to modify and maintain, and 2) it would be possible to reuse the primitive modeling elements In the following sections, first we will present the motivating example showing the limitations of current design methodologies. Next we will introduce the problem of model reuse versus component reuse. We will then outline the solution we propose which is based on a hardware version of an existing behavioural software pattern: the Iterator. This will lead to the definition of a basic component library that will later be used to reengineer the motivating example. In section 3.4 we will describe implementation details of this pattern. Some experimental results will be shown in section 4. Finally, we will present some conclusions and draw future related work.

Embracing change

Let us consider the design of a simple real-time image processing application. The whole system would be composed of the entities shown in figure 1: camera, video decoder, image processing circuit, VGA coder, and video monitor.

The image processing circuit would be composed of an input buffer to acquire the video stream, an image processing algorithm and an output buffer to accommodate the output video stream. For the sake of clarity, we will first consider the case of the simplest possible algorithm: copying data from the input buffer to the output buffer. Such a simple algorithm may be implemented as a finite state machine handling the buffer signals and sequencing the read and write operations.

Let's suppose there is a small change in the system. The input video stream is now fed into a RAM, storing a whole frame instead of using a sequential access buffer. The stream copy algorithm does not change at all: we still need to transfer data from the video source to the video sink. But the implementation must be radically changed to accomodate the new interface requirements of the memory. Now there is a need to maintain a memory address register pointing to the appropriate position in RAM. A similar situation arises if we change the output buffer to the VGA decoder into another RAM block.

Pixel format is another kind of critical modification when trying to reuse a system like the one described. Changing 8bit grayscale format into a 24-bit RGB format, for example, may require non-trivial modifications in the state machine specification, since obtaining each pixel may require more than one memory access.

Although it seems feasible to reuse the copy algorithm in many scenarios, it is not so easy because of the coupling between algorithms, data structures and hardware interface handling.

In this paper we propose to decouple algorithms and data structures by means of a hardware version of a well known design pattern: the iterator pattern [START_REF] Gamma | Design Patterns: Elements of Reusable Object-Oriented Software[END_REF]. The main goal of this pattern is to avoid exposition of the internal implementation when accessing a data structure. The hardware interface of data structures will only be exposed to iterators and components which implement those data structures. Both are either automatically generated or reused. The impact on the overall design of modifying hardware interfaces is thus minimized.

Model Reuse

Increasing reuse opportunities is a well-known problem for software designers as it is for hardware designers. Nonetheless current software and hardware engineering practice embraced different approaches to this problem. Software designs are usually modeled after a set of proven solutions to recurrent problems called design patterns. This approach differs from the component-based reuse usually found in hardware designs in that the design patterns do not specify unnecessary implementation details. Therefore, design patterns allow the reuse of higher level abstractions in a wide variety of scenarios without the performance overhead of behavioural IPs.

Several authors have already proposed translating some of the design patterns concepts to hardware design [START_REF] Damasevicius | Application of design patterns for hardware design[END_REF][START_REF] Yoshida | Design patterns applied to object-oriented soc design[END_REF][START_REF] Astrm | Design patterns for hardware datapath library design[END_REF] but to our knowledge all previously published works are entirely devoted to structural and creational patterns, already similar to current hardware design practice. In this paper we introduce behavioural patterns in the domain of hardware design, allowing a more abstract view of the design.

We do not advocate a complete parallelism between software and hardware design process. Many of the most successful design patterns do not have a hardware counterpart. Therefore there is a need to develop a hardware version of a design pattern catalog, similar to what is already available in software [START_REF] Yoshida | Design patterns applied to object-oriented soc design[END_REF]. Similarly, there is a strong need to develop standardized foundation libraries combining the most successful patterns in an integrated way.

The iterator pattern

The iterator [START_REF] Gamma | Design Patterns: Elements of Reusable Object-Oriented Software[END_REF] design pattern (figure 2) is already found in most software foundation libraries. Iterators provide a way to access the elements of a data store (aggregate object) without exposing its undelying representation.

The hardware version of entity Iterator defines an interface for accessing and traversing elements, as shown in table 2. ConcreteIterator implements the Iterator interface and keeps track of the current position in the traversal of the Aggregate. Due to the static nature of hardware some of the details of the software Iterator are not applicable. For example, the Aggregate is not responsible for creating Iterator objects. Iterators must be instantiated at design time.

Basic Component Library

In a hardware design, data storage is based on a wide range of memory technologies. Some require sequential access, others are accessed randomly, or even associatively. Besides, there are lots of algorithms performing common data manipulation (copy, transform . . . ). Others are specific to an application domain (e.g. pixel-wise filtering, lution filtering or binary image labelling for image processing applications). All those elements should be packed into a library of basic components, in a similar way to software foundation libraries. Designs built over this kind of libraries are proven to easier to develop and maintain, and less errorprone.

In the remaining of the current section, we will introduce a proposal of such basic library, inspired on the C++ Standard Template Library [START_REF] Stepanov | The standard template library[END_REF]. This library is organised around three kinds of concepts: containers, iterators and algorithms.

Containers

Containers are equivalent to the Aggregate objects in the Iterator Pattern. They are collections of elements that can be implemented in a number of physical structures. Containers are accessed through iterators. set of containers depending on the type of memory access required (random or sequential), and the type of traversal allowed (forward, backards or both).

Iterators

Table 2 shows the set of operations allowed for each type of iterator (forward, backwards or bidirectional). All iterators keep track of their current position in the traversal of the container. They are also able to read and/or write the element at that position. Forward iterators include an additional operation to advance the current position. Backward iterators include the possibility to move backwards. Random iterators can set arbitrary positions through the index operation. Although the iterator provides a common interface for any container, it must have a deep knowledge of the internals of the container. For that reason a concrete iterator must exist for each type of container in the library.

Algorithms

The basic components library should also include a set of commonly used algoritms. Every one should use the interface provided by iterators to access data in the containers. This would guarantee reusability of the algorithm, despite of the container chosen for a certain implementation. It is out of the scope of this paper to delimit the set of algorithms that should be included in the basic library. For illustration purposes we have just selected two simple ones: copying data from a source to a destination, and an image blur filter.

The Example Revisited

Lets apply the iterator pattern to the example described in section 2. Figure 3 shows the resulting model. Now data acquisition from the video decoder has been modelled as a read buffer container (rbuffer), while the output video stream is fed into a write buffer container (wbuffer). Access to rbuffer and wbuffer containers is abstracted through rbuffer it and wbuffer it iterators respectively. Therefore, the video processing algorithm avoids direct manipulation of the containers. As seen in figure 3, containers are implemented over FIFO structures (note rbuffer and wbuffer fifo suffixes) that accomodate the data stream. The copy algorithm is almost trivial: an endless loop that sequences read and write operations and iterator forwarding for both containers. All these operations can be performed in parallel in a hardware implementation. Note that the simplicity of the algorithm does not affect the validity of our approach, that can be generalized to any other video processing algorithm.

Lest's suppose that the system must be modified for a new configuration, where both input and output streams are fed into two separate static RAMs. This change does not really affect the model, since the specific aggregates remain the same (wbuffer and rbuffer). Therefore, the other elements in the model are not affected either, and no modifications are needed. The only difference is that the aggregates must be implemented over static RAM instead of on-chip fifos. This implementation can be automatically generated as described in section 3.4, so this kind of modifications requires no design effort.

It would also be possible to modify the pixel data representation (from 8-bit grayscale to 24-bit RGB, for example).

Here two different alternatives arise depending on the RAM data bus size: 1) For a 24-bit data bus, we should only regenerate the implementations of the elements using the 24bit data pixel as the base type. 2) For an 8-bit data bus, we should also modify the iterator code to perform three consecutive container reads/writes to get/set the whole pixel. In any case, all this scenarios can be considered by the automatic code generator, thus requiring no designer intervention.

Pattern Implementation

Most design patterns are naturally described using the object-oriented (OO) paradigm . While there exist several hardware description languages with a limited support of OO concepts (e.g. SUAVE [START_REF] Ashenden | Object-oriented extensions to vhdl[END_REF], SystemC [START_REF] Arnout | Systemc standard[END_REF]), synthesis tools that are able to generate a final implementation from a hardware OO model are not mature at all, despite this is an active research area [START_REF] Schulz-Key | Object-oriented modeling and synthesis of systemc specifications[END_REF].

On the other side, traditional hardware description languages, such as Verilog or VHDL, do not support some of the necessary abstractions. Direct translation of the proposed pattern would require at least: inheritance support, a broader sense of genericity, and support for partial template specialization.

Our solution is based on the concept of metaprogramming [START_REF] Sheard | Accomplishments and research challenges in metaprogramming. In 2nd InternationalWorkshop on[END_REF]. An automatic code generator produces customized versions of containers and iterators from a code template. The template includes information on the available operations, shared resources and parameterized code fragments. The result is a set of efficient VHDL components, ready to be synthesized. Algorithms can be also described through metamodels, although they have not been considered in this paper and are left as future work. The code generator must also be able to implement communication mechanisms for complex data types whose sizes do not match that of the ports between components (such as the modification of the pixel format discussed in 3.3). It is also the responsible for including only those resources that are really used by the selected operations.

Metaprogramming provides a number of additional benefits. It allows automatic generation of arbitration logic for shared physical resources (e.g. RAM). It also provides transparent selection of the communication protocol between components. Here transparecy refers to the model, not to the designer that must select the right values for the different parameters considered in the metamodel.

As outlined in section 3.2, containers may be mapped to several physical devices. All of them can be implemented in any kind of RAM memory, while stacks can also be implemented over FIFO cores, or queues and read/write buffers can also mapped over LIFOs (these cores are commonly found in FPGA designs).Some targets provide the most efficient implementation (such as a queue over a FIFO core), while others may lower the overall system cost (such as the same queue over an external RAM).

Metaprogramming defers until the last moment the selection of the proper implementation of a container, depending on the requirements of the application. However, this selection may be based on previous characterization of the design space. For example, in this paper, we characterized all the physical devices available in the target platform (the XSB-300E prototype board from XESS ). We obtained information about data access times for every container, area, power comsumption . . . . Since components are generated automatically, it is feasible to generate versions of each one for every physical target and range of configuration parameters. This characterization of the design space would delimit the region of interest given a certain set of constraints.

Only specific classes have a physical counterpart, when mapping the abstract model of the design pattern over the implementation. Each one becomes a VHDL entity and an architecture. Abstract classes do only exist inside the domain of the and are used to define a common functional interface. The physical interface (that of the VHDL entity), includes not only the functional interface, but also an extra implementation interface, that includes, among others, all the ports to interface the physical devices. The physical entity of a container inmplemented over a static RAM, for example, will include a port for each operation and each parameter from the functional interface (read, empty . . . ), in addition to all the ports related to the SRAM interface (p addr, p data . . . ). The VHDL architecture of the container will define the logic to perform the mapping.

Figures 4 and5 show the entities implementing the container rbuffer used in the example in section 3.3. The first one belongs to the implementation over a FIFO, while the second one includes only the differences (the implementation interface) with respect to the first.

The VHDL architecture is simply a wrapper of the FIFO core in the first case, and hardly includes any logic. In the second case, the architecture encloses a little finite state machine that controls memory access, as well as a few registers to store the begin and end pointers of the queue (implemented as a circular buffer) over the static RAM.

Iterators are also generated from their own metamodel. One iterator metamodel must be defined for each kind of container. The metamodel is the responsible for providing the necessary functionality, depending on the type of traversal and on whether it is an input or an ouput iterator. The iterators used in the previous example don't include much functionality since they are extremely simple. In fact they are no more than a wrapper that renames some signals and provides the common interface already mentioned.

The implementation of the copy algorithm is really simple, since it only has to activate the inc and read operations for the input iterator, and the inc and write operations for the output iterator. The data is also connected from the input to the output.

Experimental Results

The numbers in table 3 show the results of the implementation of three design examples using the Iterator pattern. As a target platform we use the XSB-300E board from XESS. Each cell shows the results corresponding to the pattern-based versus the custom implementation. The first two rows correspond to the example revisited in section 3.3. The third example is a little bit different. In this case, we have implemented a blur filter that processes an image coming from the video decoder and sends it to a VGA coder. The rbuffer container, instead of a simple FIFO has been mapped over a special one. It is a 3-line buffer structured to provide 3 pixels in a column for each access. This makes the convolution product in the blur algorithm very simple and quite efficient since ideally a new filtered pixel can be generated at each clock cycle.

It is clear from the results in the table, that there is a negligible overhead for the pattern-based implementation. The use of the pattern affects only the structure of the model, but does not necessarily imply extra logic. This is for example the case of the iterators, which are only wrappers that will be dissolved at the time of synthesizing the design. In the above examples, ad-hoc solutions contain almost the same physical components (FIFOs, algorithm FSM . . . ).

The saa2vga examples represent two different points of

Conclusions and Future Work

The use of IPs has proven to be a very effective way of managing the ever growing complexity of SoCs. However, system integration is only a part of the design problem. Higher level design methodologies, where solutions are considered in the domain of the problem without being conditioned by the implementation must be provided. This is recently attracting the interest of the research community to some of the most successful paradigms used in software design, such as OO Programming, UML and design patterns.

The application of such technologies is not straightforward, due to the important differences between both domains, but some contributions have been done to the use of UML for system level design[5, or the synthesis from an object-oriented specification [START_REF] Schulz-Key | Object-oriented modeling and synthesis of systemc specifications[END_REF]. Also some papers have already considered the applicability of design patterns to hardware design. However, the fact that design patterns are based on the object-oriented paradigm, and the lack of a mature technology for OO-synthesis, makes that only structural patterns are considered, since they are easily mapped over a hardware description language.

In this paper we propose the use of a well known software design pattern (the Iterator) to provide a way to decouple algorithms from the underlying data structures. This would make algorithms more generic and thus provide more opportunities for later reuse. Unlike previous proposed hardware design patterns, the iterator is behavioural, and requires a higher level of abstractions that the one provided by HDLs.This have been solved through the use of metaprograming. Also a basic components library based in this pattern has been proposed. This library provides eficient physical implementations for sequential and random data structures. The deliberate simplicity of the examples shown in the paper proves the flexibility and low overhead provided by this modelling approach.

Along the paper, we raised a number of questions that must be addressed. There is a need to develop a hardware version of a design pattern catalog, similar to what is already available in software. Specific application domains such as video image processing demand specific libraries including common algorithms (convolution filters, image labelling . . . ). and specialized iterators. A hardware abstraction layer should be considered for the development of the metamodels.

Figure 1 .

 1 Figure 1. Design example

Figure 2 .

 2 Figure 2. Iterator pattern

Figure 3 .

 3 Figure 3. Model of the example

Figure 4 .

 4 Figure 4. Read buffer over a FIFO device

Figure 5 .

 5 Figure 5. Read buffer over an SRAM device

Table 1

 1 classifies the basic

Table 1 . Common containers Containers Random Sequential Input Output Input Output

 1

	stack	-	-	F	B
	queue	-	-	F	F
	read buffer	-	-	F	-
	write buffer	-	-	-	F
	vector	✔	✔	F, B	F, B
	assoc. array	✔	✔	-	-

Table 2 . Iterator Operations Operation Meaning Applicability

 2

	inc	move forward	F / F, B
	dec	move backwards	B / F, B
	read	get the element	random / F, B
	write	put the element	random / F, B
	index	set the current position	random

Table 3 .

 3 Design experiments.

	Design	FFs	LUTs	block	clk
				RAM MHz
	saa2vga 1	147/147	169/168	2/2	98/98
	saa2vga 2	69/69	127/127	0/0	96/96
	blur	3145/3145 4170/4169	2/2	98/98
	the design space. The first one (the FIFO implementation)
	provides maximum performance at the highest cost. The
	SRAM implementation is much smaller, but performance
	will depend on memory access times.

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

Proceedings of the Design, Automation and Test in Europe Conference and Exhibition (DATE'05)