Amr T Abdel-Hamid

Sofiène Tahar
email: tahar@ece.concordia.ca

El Mostapha

A Public-Key Watermarking Technique for IP Designs

Sharing IP blocks in today's competitive market poses significant high security risks. Creators and owners of IP designs want assurances that their content will not be illegally redistributed by consumers, and consumers want assurances that the content they buy is legitimate. Recently, digital watermarking emerged as a candidate solution for copyright protection of IP blocks. In this paper, we propose a new approach for watermarking IP designs based on the embedding of the ownership proof as part of the IP design's FSM. The approach utilizes coinciding as well as, un-used transitions in the state transition graph of the design. Our approach increases the robustness of the watermark and allows a secure implementation, hence enabling the development of the first public-key IP watermarking scheme at the FSM level. We also defin evaluation criteria for our approach, and us experimental measures to prove its robustness.

I. INTRODUCTION

Fast advancing IC (integrated circuit) processing technologies have enabled the integration of full systems an a single chip forming the new paradigm of the "System-on-a-Chip" (SOC) technology. Reusable virtual components or Intellectual Property blocks (IPs) are most effective when it comes to reducing cost and development time of SOC designs. IP designs are a big investment for companies, on the other hand, sharing IP designs pose significant high security risks. Most of these IPs need time and effort to be designed and verified, but they can be copied, or modified to cover the authorship proof. Creators and owners of IP designs want assurances that their content will not be illegally redistributed by consumers, and consumers want assurance that the content they buy is legitimate.

The VSI Alliance IP protection development working group [START_REF]Intellectual Property Protection: Schemes, Alternatives and Discussion[END_REF] identifies three main approaches to secure IPs: deterrent, protection, and detection. The first uses legal means, such as patents, copyrights or trade secrets to stop attempts for illegal distribution. The second prevents the unauthorized usage of the IP physically by license agreements and encryption. The third detects and traces both legal and illegal usages by using watermarking and fingerprinting. Protection techniques do not track the design in order so check if the buyer resold it, or even reused it without permission. They also cannot stop local leakage, such as employees or sub-contractors. Like digital media, watermarking IPs emerged as the most effective solution for tracking IP designs after sales, where the owner has a strong enough evidence to be used in front of court.

In this paper, we propose an IP watermarking approach that can be used early in the design cycle, and which is based on the finite state machine (FSM) of the IP. FSMs model the transformation between inputs and outputs of the IP design and can be represented in different forms, such as state transition graphs (STG). FSM watermarking enables the detection of inserted watermark at lower implementation levels.

We propose a watermarking approach in which both existing and unused transitions in the FSM are used to embed the signature. In case no free transitions are available (completely specified FSM, CSFSM), we add extra input bits to insert the watermark. Using existing transitions provides a supraliminal channel 1 as it would give more strength to the system against different attacks. It also helps balancing between adding enough data to identify the owner and the design overhead (area, power, delay) this data may introduce.

The rest of the paper is organized as follows: Section II gives a brief description of related work on IP watermarking. Section III presents our IP watermarking and extraction techniques. Section IV provides measures used to evaluate the performance of our approach, and to analyze the attacks. Section V presents a prototype implementation of the algorithm, including different experimental results. Finally, Section VI concludes the paper.

II. RELATED WORK

There are many IP watermarking or fingerprinting techniques available in the open literature. They fall into two classes [START_REF] Abdel-Hamid | Hardware IP Watermarking for Copyright Protection[END_REF]. Dynamic watermarking, where the watermark is detected by running the watermarked IP and detect the generated signal. Static watermarking, where the watermark is considered as a property of the design, and can only be detected by different static techniques.

Kahng el al. [START_REF] Kahng | Constraint-Based Watermarking Techniques for Design IP Protection[END_REF] proposed and experimented a constraintbased IP watermarking as one of the leading static approaches. The approach is a generic algorithm that can be used at different levels of the design flow. It is based on available tools used mainly to solve NP-hard problems. This was done by adding a set of well defined extra constraints that generate a watermarked solution for the problem. The approach was tested and applied to different levels of the IP design. At the system level for instance, it was used for the watermarking of memory graph coloring solutions by Hong et al. [START_REF] Hong | Techniques for intellectual property protection of DSP designs[END_REF]. At lower design levels, the approach was used even more effectively in routing [START_REF] Narayan | IP Protection for VLSI Designs Via Watermarking of Routes[END_REF], placement, and floor planning [START_REF] Kahng | Constraint-Based Watermarking Techniques for Design IP Protection[END_REF].

The main advantage of the approach is its real low overhead on the design cycle, as the NP-hard problem will be solved anyway. The approach however, has two main drawbacks. First, tracking the watermark is not that easy if the design is resold at other abstraction levels. Also, imposing extraconstraints on a design procedure might not be as successful as thought by the authors. Finally, Le et al. [START_REF] Le | Cryptanalysis of UCLA Watermarking Schemes for Intellectual Property Protection[END_REF] showed that several constraint-based watermarking schemes can be broken easier than previously thought.

At the behavioral level, Oliveira [START_REF] Oliveira | Techniques for the Creation of Digital Watermarks in Sequential Circuit Designs[END_REF], and Torunoglu et al. [START_REF] Torunoglu | Watermarking-Based Copyright Protection of Sequential Functions[END_REF] introduced two different techniques used in the watermarking of sequential parts of the design. Both algorithms are based on adding new input/output sequences to the FSM representation of the design. The main advantage of both approaches is the ability to detect the presence of the watermark at lower design levels.

The algorithm in [START_REF] Torunoglu | Watermarking-Based Copyright Protection of Sequential Functions[END_REF] is mainly based on extracting the unused transitions in a STG of the behavioral model. These unused transitions are inserted in the STG associated with a new defined input/output sequence which will act as the watermark.

The approach in [START_REF] Oliveira | Techniques for the Creation of Digital Watermarks in Sequential Circuit Designs[END_REF] tries to manipulate implicitly the STG, where the user changes the design to include the watermark as a specific property, which is rare in non-modified STGs. The extra states added can be removed using a state reduction approaches. The author in [START_REF] Oliveira | Techniques for the Creation of Digital Watermarks in Sequential Circuit Designs[END_REF] proposed to solve this problem by slightly changing the functionality of the STG. This also cannot be done mechanically as it might affect the design functionality.

III. WATERMARKING FSMS USING COINCIDING

TRANSITIONS As a passive technique, one of the main challenges of watermarking schemes is the authenticity of the watermark. In the scheme we propose in this paper, this problem is solved by using a secure third party, e.g., a watermarking governing body. This governing body will be responsible for generating and distributing time-stamped authenticated signatures, as well as keeping a record for such signatures for the extraction phase.

The proposed watermarking scheme is composed of three main parts: Signature generation, watermark insertion (embedding), and watermark detection (extraction). The watermark embedding phase is done by the designer, where he/she uses the authentic signature to embed the watermark using the embedding algorithm proposed below. Finally, in the manufacturing facilities and afterwards, the designer introduces the key needed to detect the watermark, in order to prove the authenticity of the design.

A. Signature Generation

The signature generation is done by the watermarking authority (third party which will prevent intruders from search-ing for ghost watermark and consider it as their watermark (known as ghost attacks). The generated signature will be also time-stamped to prevent intruders from re-embedding their watermark in the system.

The secure third part will use the ownership information provided by the IP designer and encrypts it using any public/private-key encryption algorithm after time-stamping it. The encrypted information is then hashed giving a short digest to decrease the watermark embedding overhead. This digest is computationally infeasible to find another message hashes the same value.

In our proposed model, the owner chooses any arbitrary length message that will prove his/her ownership and encrypts it using his own private key of any encryption algorithm. The encrypted message is then hashed to shorten it to a certain length using a one-way hash function, MD5 [START_REF] Rivest | RFC 1321: The MD5 Message-Digest Algorithm[END_REF] in our case, to generate a constant length bit sequence (128 bits) as a proof of ownership, if using MD5.

B. Coinciding Transitions Approach: Output Mapping

The watermark insertion algorithm attempts to coincide a part of the watermark on the STG transitions to increase the watermark robustness. This is done by searching different outputs of each visited state in the STG, and comparing it to a part of the generated signature in order to map this signature on the system outputs. Starting form any randomly chosen state (S x ), the watermark will be added to the STG according to the following steps:

1) Compare the outputs of the state S x to the generated signature to check if they coincide. 2) In case one of the outputs is equal to the watermark bits, this transition will be considered part of our watermark. 3) If the signature sequence is not equal to any of the outputs, then the inputs of S x will be checked to determine if there is any free input that can be used to add an extra transition. The next state in this case will be chosen randomly, with preference given to states with free transitions. 4) In case all the inputs are already being used, an extra input bit e i wm is added to the system to extend the FSM. This input bit will have the same logic value for all already existing transitions. For instance, a logic value '0' assigned to the already existing transitions and logic value '1' will be used for the watermark transition added. The next state will be chosen randomly. 5) The algorithm will loop until embedding all the signature bits is done. Figure 1 illustrates an example for the above algorithm using the signature in the bottom of the figure. Starting from state (S0), the tool finds a coinciding output (00) and moves to S3. In S3 no putput 11 exists but input 00 is free. The next state in this case will be decided randomly and the algorithm advances to state (S2). In S2, all inputs are being used, hence an extra input bit is added to extend the whole STG. This bit will be forced to be equal to "0" for existing transitions out of S2 and "1" for added ones. This extra transition will drive the STG to state (S0) randomly as well. The algorithm does not search the system states of the STG to insert the watermark, it simply inserts the watermark directly on a randomly chosen state. This makes it fast and would not cause high overhead on the design flow. It was noted that the number of coinciding transitions will decrease as the number of outputs increases. This happen as the probability to find a number of outputs equals coincide with the watermark decreases as the number of output increases. To solve such problem, the algorithm works into iterations. Each iteration works with different number of outputs, and tries to coincide more transitions. Afterwards, the tool decides between the generated solutions based on the robustness, as well as lower design overhead introduced, as discussed in the next section.

C. Watermark Extraction

The third phase of the watermarking process is tracking the watermarked design. In the proposed watermarking technique, direct detection can be used through the previously generated input in the watermarking process to generate the output signature. Using direct detection, as proposed in [START_REF] Torunoglu | Watermarking-Based Copyright Protection of Sequential Functions[END_REF], will not enable the owner to detect the output in the correct form [START_REF] Abdel-Hamid | Hardware IP Watermarking for Copyright Protection[END_REF] in case of masking attacks, discussed in details in the next section. Traces of the watermark still exist and it is enough to be considered as an evidence in front of a court. In such case, rebuilding the whole FSM is the ultimate solution to extract all the traces left from the watermark, but this is an expensive and complicated task.

In our approach, coinciding transitions cannot be deleted. This will give the system extra robustness as the attacker will have to decide between used and unused transitions. This algorithm will force the attacker to delete all extra added transitions in the system. A very hard process with a very low probability, defined as a measure of robustness in the next section. The algorithm still needs to be optimized in order to decrease the search time. Yet, it shows an extra advantage of using coinciding transitions.

IV. EVALUATING WATERMARK PERFORMANCE

Petitcolas [START_REF] Petitcolas | Watermarking Schemes Evaluation[END_REF] identified a set of measures for watermark evaluation. These measures were developed mainly for multimedia applications but still some of them are essential for the evaluation of IP watermarking techniques. These measures are described briefly in the next subsections. For further information about attack analysis and other measures the reader can refer to [START_REF] Abdel-Hamid | Hardware IP Watermarking for Copyright Protection[END_REF].

A. Impact on Design Functionality

Perceptibility [START_REF] Petitcolas | Watermarking Schemes Evaluation[END_REF] is a measure of how much the hidden mark has deteriorated the perceived quality of the system. In hardware design, designers cannot accept behavior changes in a system due to watermark insertion, i.e., watermarking technique should not interfere with the original system operation. The following theorem proves the soundness of the watermarked design automaton M wm with respect to the original behavior M .

Theorem 1: The watermarked design M wm behaves exactly as the original design M for any set of arbitrary inputs, under the condition that all extra added bits e wm , used for watermarking, are set to the same secure logical level defined at the watermarking insertion stage.

Let ã be any arbitrary input sequence composed of m elements, such that ã = (a 0 , a 1 , ...a m-1 ). ãwm is the same input sequence for the watermarked design, where ãwm = ã, e wm , then: ∀ ã e wm . e wm = C → (λ(q 0 , ã) = λ wm (q 0 wm , ãwm )) where C is a secure constant logical value for all extra added bits pre-defined at the time of inserting the watermark, q 0 wm is the initial state of the watermarked design. The theorem is proved mathematically in [START_REF] Abdel-Hamid | Hardware IP Watermarking for Copyright Protection[END_REF]. It is proved that under the above conditions, the initial state in both designs will behave identically. And then proved that the output functions (λ and λ wm ) will produce the same values for any given set of input sequence.

B. Reliability and Attack Analysis

The level of reliability [START_REF] Petitcolas | Watermarking Schemes Evaluation[END_REF] is divided into two main aspects. Robustness, which measures the strength of the hidden mark against attacks, and false positive, which defines the probability a watermark detector can find an ownership mark in a non-watermarked design. In the case of public-key operation, the level of reliability should include more measures for asymmetry robustness [START_REF] Petitcolas | Watermarking Schemes Evaluation[END_REF].

1) Attack Analysis: Digital watermarking attacks are categorized in four main classes [START_REF] Cox | Digital Watermarking[END_REF]: unauthorized removal, unauthorized embedding, unauthorized detection, and system attacks. The same categorization applies for IP watermarking schemes. System attacks aim at attacking the concept of watermarking itself, as an example, attacking the cryptographic base of the watermarking, or removing the chip that checks the watermark physically in case of video for instance. This kind of attacks cannot to be avoided by the watermarking schemes. Yet, the VISA IP protection group solves this by protecting the design through different transactions.

Embedding attacks, aim at embedding another watermark in the design (watermark re-embedding) or try to find a ghost watermark that can be considered an intruder watermark (ghost searching). As for most of the well known watermarking schemes, we are proposing a third entity (a secure third party) that is responsible for granting and authorizing an embedded time-stamped signature (ownership certificate). These two measures will prevent both embedding attacks, because the intruder will be forced to extract a 128 pre-defined bits (if using MD5) from the system, that totaly coincide with his signature. The probability of finding ghost signatures is directly related to the probability of finding false positives as it will be discussed in the next subsection, and is extremely small. On the other hand time-stamping will stop the intruder from re-embedding his/her watermark in a previously licensed system, because the database of the third entity will directly reveal the real owner.

Removal attacks, [START_REF] Cox | Digital Watermarking[END_REF] aim at the removal of the watermark information. This is attempted without breaking the security of the watermark. Removal attacks are divided into either elimination attacks or masking attacks. Coinciding transitions are considered as supraliminal channels. The probability of watermark deletion is defined as following "probability that an attack changes or deletes extra added transitions without deleting at least one original transition".

This probability will differ depending on both detection and operation modes. In the symmetric (secret) mode, this probability will be related to the total number of design transitions (n), in the case of asymmetric mode, the probability will be related to the number of the watermark transitions, as the intruder will be able to know these transitions.

To Remove the watermark, the intruder need to delete most of the extra transitions (m 2 ) without deleting any of the originally existing transitions (n) to delete the watermark. Thus, the removal probability of the watermark (P r ) defined as " probability that any attack would change or delete all extra added transitions (m 2 ) without deleting at least one original transition". As discussed above this probability depends on the mode of operation (symmetric or asymmetric). In the symmetric mode, the intruder needs to choose from n existing transitions, so that P s r is defined as:

P s r = 1 C m2 n+m2 where, C k j is the combination of k and j, such that C k j = j!/(k! × (j -k)!).
On the other hand, in the public-key organization, the intruder does not need to choose from the n originally available transitions, but from m watermarking transitions. This means that the removal probability (P a r ) here will be calculated as:

P a r = 1 C m2 m
Asymmetric techniques in general are not considered as robust as symmetric ones [START_REF] Petitcolas | Watermarking Schemes Evaluation[END_REF]. The main measure of our approach capability to work in an asymmetric (public-key) mode is P a r . Depending on such measure, the system cannot work in the public mode unless this probability is smaller than a certain value defined by the designer. This is done, by choosing between different iterations that will satisfy the probability condition and has the minimal design overhead. It is worth to be mentioned that a second secret watermark can be added to the system in case the intruder could break the public one. This will add extra overhead to the system, but will be rewarded by a higher level of security.

2) Detecting False Positives: The probability of coincidence, is defined as a main measure of the authenticity of the watermark. This probability is considered as a measure for detecting the watermark in a design by accident in a nonwatermark design (false positives). In [START_REF] Torunoglu | Watermarking-Based Copyright Protection of Sequential Functions[END_REF], the probability of coincidence (P u ) for an FSM was defined as "the odds that an unintended watermark is detected in a design". It is also considered a measure for the ghost attacks discussed above. This probability was calculated under the approximation that all the transitions have the same probability of occurrence as:

P u = 1 [2 |∆| ] x -1 n ≥ 1
where x is the number of extra added transitions and | ∆ | is the total number of possible outputs. In our system, we are only adding m 2 extra transitions, but the owner still needs a sequence of length m to detect the watermark.

Using the MD5 hash function, a constant number of bits for the watermarking sequence (128 bits) is introduced. m is calculated as the upper limit of the division of the number of added bits by the number of outputs, i.e., m = 128 |∆| . We can then calculate the lower bound of the coinciding probability, the worst achievable case, ( Pu ) as:

Pu = 1 [2 |∆| ] 128 |∆| -1
Hence,

P u Pu = 1 2 128 -1 = 2.938 × 10 -39
This means that we can safely state, that our probability of coincidence is nearly constant and is larger than the above value for the 128 bits signature used. If the designer needs a lower value for P u , he/she can either change the hash function used, or re-watermark the design using the same technique again with a second signature.

C. Watermarking Overhead

Watermark approaches rely on embedding signatures generated from hash functions in order to decrease the watermarking process overhead. In our particular case, the number of bits added by using MD5 hash function is equal to 128 bits. This amount can be increased at the expense of the number of input bits as well as the area and extra logic added to the system. Mapping more coinciding transitions directly means that we will have less overhead. The watermarking overhead is divided into three different issues: area, delay, and power. We have measured the percentage of increase on a number of benchmark designs before and after watermarking. The results are shown and discussed in the experimental results to follow.

V. IMPLEMENTATION AND EXPERIMENTAL RESULTS

A. IP Watermarking Tool

A Prototype for the algorithm was built to test its performance. The tool [START_REF] Abdel-Hamid | A Tool for Automatic Watermarking of IP Designs[END_REF] was implemented using C++ under Unix environment. The design accepts FSMs in kiss2 format [START_REF] Sentovich | SIS: A System for Sequential Circuit Synthesis[END_REF], which can be generated by many tools such as SIS [START_REF] Sentovich | SIS: A System for Sequential Circuit Synthesis[END_REF]. Figure 2 shows the different implementation blocks. The tool is composed of four main blocks. We started by building a tree for the FSM representation using the FSM builder block. The signature generation block provides the signature to the watermarker block after hashing it, while the random input and next states needed are provided using a random generator built in our tool. In the watermarker block, the user can choose the number of iteration the algorithms can run to watermark his/her design. The watermarker block also includes a decision block that chooses between iteration results using the highest probability P a r that is smaller than a certain value defined by the user (10 -6 in our case). The choice takes into consideration the lowest overhead possible (least added transitions, and lowest number of added bits). Finally, using the Kiss-to-HDL block [START_REF] Abdel-Hamid | A tool for Converting Finite State Machine to VHDL[END_REF], a synthesizeable watermarked VHDL code is generated.

B. Experimental Results and Comparison

To evaluate our approach, the algorithm was applied on the IWLS93 [START_REF] Mcelvain | LGSynth93 Benchmark Set: Version 4.0[END_REF] benchmark set using the FSMs generated by the available SIS tool. Table I the watermark in each design is given in ms. The algorithm adds the transitions without building the whole design tree, to decrease the time needed to watermark a design. On the other hand, the random generator favors states with free transitions, higher seeds for such states, but this did not prevent uin adding an input although the design is NCFSM, such as in the case of EX1. The time for inserting the watermark is extremely short, hardly exceeded 8 seconds in the case of scf with 54 iterations involved, which gives a good indication about the low overhead the algorithm can introduce in the design cycle.

Table I evaluates the performance of the algorithm. This is done by calculating the different probabilities shown before in section IV. The removal probabilities (P s r and P a r ) are shown. Table I shows the area, power, and delay overhead compared to the synthesized original circuit. The experimental results demonstrate that the table that our approach has a very low effect on the delay and power, especially when the design tend to get larger. On the other hand, the area has high overhead for small designs, then decreases as the designs get larger. This is due to the large signature size compared to the original circuit. As for the robustness of the system, the algorithm failed to watermark some designs efficiently, either it could not coincide transitions, such as for S1488, which cannot operate in public-mode. This can be solved by changing the signature generated or re-watermark the design, but this will result on higher design overhead.

It is worth mentioning that, the probability of coincidence P u is nearly constant and less than 2×10 -39 . Also, increasing the coinciding transitions (m 2 ) will directly increase the robustness of the system in the public-key case, yet it lowers the robustness of the system in the secret-key mode. Obviously, the overheads decreases, as the design size increases.

VI. CONCLUSIONS

Sharing IP blocks in such a competitive market poses significant high security risks. Digital watermarking has emerged as a candidate solution at the detection phase of copyright protection for IP blocks. In this paper, we proposed, analyzed, and implemented a novel approach for watermarking sequential IP designs. The approach was based on the utilization of coinciding transitions as well as the unused transitions of the design FSM in order to give higher robustness. The approach works in a public-key organization, where the detection key can be shared with non-trusted parties.

We also defined different parameters needed to evaluate the approach and tested it using experimental results with the IWLS93 benchmark. The implemented algorithms are fast and have a comparatively low overhead on the design, which would help it to be integrated easily in the design cycle.

The main drawback of our approach is that it works on flat FSMs, which is not the case when it comes to real designs. We are in the course of extending the approach to handle hierarchal designs, in order to ease its integration.

2 ) 3 )

 23 To solve masking attacks, we propose an extraction algorithm making use of coinciding transitions as marks, or semaphores, to detect if the watermark traces exist. The extraction algorithm is as following: 1) During the embedding of the watermark, the tool builds an extra file containing different input/outputs pairs (different sequence paths) that lead to the coinciding transitions. During the extraction, if direct detection fails. The extraction tool will start by checking the previously defined paths and check the availability of coinciding transitions. To find a coinciding transition, the tool will search for all the extra added transitions that might exist around this state. 4) The extraction tool searches all the coinciding transitions and extracts all non-deleted extra transitions in the system.

Fig. 2 .

 2 Fig. 2. Watermarking Prototype Structure

TABLE I IWLS93

 I BENCHMARK RESULTS USING OUTPUT MAPPING ALGORITHM

	Circuit	I[O]	T[S]	e wm m	m 1 m 2 C/NC N	t	P s r	P a r	Area% P ower% Delay%
	MC	3[5]	10[4]	2	33	17	16	C	3	455	3.770e-12	8.570e-10 323	28.6	2.4
	LION	2[1]	11[4]	1	128 116	12	C	1	35	1.500e-17	4.214e-17 240	17.307	0
	DK27	1[2]	14[7]	2	64	48	16	C	1	85	5.814e-17	2.046e-15 153.2	19	3.6
	EX4	6[9]	21[14]	0	26	13	13	NC	6	416	E7.1084e-12 9.614e-8	29.3	23.4	5.8
	OPUS	5[6]	22[10]	0	22	9	13	NC	4	149	1.926e-11	2.010e-6	34.9	13.2	6.3
	DK15	3[5]	32[4]	1	34	21	13	C	3	146	4.890e-14	1.077e-9	92.8	17.2	1.8
	S27	4[1]	34[6]	1	128 125	3	C	1	133	1.4377e-6	2.929e-6	36.2	3.7	0
	SSE	7[7]	56[16]	1	19	6	13	C	5	214	1.268e-24	5.918e-15 29.2	14.2	2
	BBARA	4[2]	60[10]	1	64	42	22	C	1	27	7.1750e-25	1.244e-17 72.3	17.3	-1.1
	S510	19[7]	77[47]	1	22	8	14	NC	4	286	2.631e-17	3.127e-6	34.2	8.9	3.2
	S1	8[6]	107[20]	1	28	13	15	C	4	485	3.251e-20	2.671e-8	31.7	14.8	3.4
	PLANET	7[19]	115[48]	1	9	4	5	C	17 829	4.441e-9	0.0079	36.2	12.4	0.9
	EX1	9[19]	138[20]	1	8	3	5	NC	17 1001 1.938e-9	0.0178	17.391	14.516	3.5
	STYR	9[10]	166[30]	1	15	7	8	C	8	566	4.094e-14	1.554e-4	13.4	15.4	1.8
	S832	18[19] 245[25]	1	7	0	7	C	17 743	1.236e-13	1	6.8	6.4	0
	S1494	8[19]	250[48]	1	8	7	1	C	17 646	8.494e-14	0.125	11.6	3.2	1.8
	S1488	8[19]	251[48]	1	7	0	7	C	17 1407 0.0038	1	14.6	3.2	0
	SCF	27[56] 166[121]	0	3	0	3	NC	51 8021 1.265e-6	1	3.5	9.8	1.4
	KIRKMAN 12[6]	370[16]	0	22	11	11	NC	10 201	1.369e-21	1.417e-6	2.1	1.6	0.5
	S298	3[6]	1096[218] 1	22	3	19	C	4	154	1.436e-41	6.493e-4	5.4	5.8	0.7
	TBK	6[3]	1569[32]	1	43	18	25	C	1	144	1.223e-55	1.643e-12 1.7	3.2	0.2

a low bandwidth channel that the intruder cannot afford to modify as it uses the most significant components of the object as a means of transition [5] 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) 1530-1591/05 $ 20.00 IEEE


Shrirang M Yardi

Michael S Hsiao

Thomas L Martin
email: tlmartin@vt.edu

Dong S Ha
email: ha@vt.edu

Quality-Driven Proactive Computation Elimination for Power-Aware Multimedia Processing *

We present a novel, quality-driven, architectural-level approach that trades-off the output quality to enable power-aware processing of multimedia streams. The error tolerance of multimedia data is exploited to selectively eliminate computation while maintaining a specified output quality. We construct relaxed, synthesized power macro-models for power-hungry units to predict the cycle-accurate power consumption of the input stream on the fly. The macro-models, together with an effective quality model, are integrated into a programmable architecture that allows both power savings and quality to be dynamically tuned with the available battery-life. In a case study, power monitors are integrated with functional units of the IDCT module of a MPEG-2 decoder. Experiments indicate that, for a moderate power monitor energy overhead of 5%, power savings of 72% in the functional units can be achieved resulting in an increase in battery life by 1.95×.

Introduction

The main challenge facing designers of battery-operated devices is guaranteeing battery-life for processor-intensive applications like portable video, audio, streaming multimedia and speech synthesis while providing the required Quality of Multimedia Data (QoMD) to the end-user. Both general-purpose and application-specific portable devices are becoming increasingly popular mainly due to their ability to support such applications. Some of the characteristics exhibited by such workloads include: (i) heavy, iterative computation using power-hungry arithmetic units, (ii) need for real time processing of the input streams, and (iii) tolerance to errors in computation that go unnoticed by human visual/auditory systems.

The property of error tolerance has been widely exploited for power and area optimization of multimedia processing hardware. Examples include use of fixed point arithmetic units [START_REF] Dobberpuhl | The Design of High-Performance Low-Power Microprocessor[END_REF], reduced bit-width floating-point units [START_REF] Fang | Lightweight Floating-Point Arithmetic: Case Study of Inverse Discrete Cosine Transform[END_REF], application-specific enhancements to the Discrete Cosine Transform (DCT) and Inverse DCT (IDCT) implementations [START_REF] August | Low Power Design of DCT and IDCT for Low Bit Rate Video Codecs[END_REF] and reformulation of canonical transform algorithms [START_REF] Wang | Fast Algorithms for the Discrete W transform and Discrete Fourier Transform[END_REF]. Recently, battery-driven power management techniques were proposed in [START_REF] Benini | Battery-Driven Dynamic Power Management[END_REF][START_REF] Lahiri | Communication Architecture Based Power Management for Battery Effi cient System Design[END_REF] that specifically

Our Contributions

In this paper, we propose an architectural-level methodology for energy-efficient processing of multimedia streams by dynamically adjusting the number of computations performed during decoding. We take advantage of the error tolerance of multimedia streams to proactively eliminate some computations, thus intentionally introducing errors during decoding, but without heavily degrading the output quality. Our key observation is that, unlike conventional techniques, relaxing the guarantee of accurate computation leads to higher power savings by trading off the QoMD. We outline a novel technique in which the power consumption of the input stream is dynamically predicted on a per-computation basis by monitor circuits, termed as power monitors. We use synthesized and relaxed power macro-models of selected power-hungry functional units as their power monitors. The degradation in playback quality is controlled by a multimedia-specific quality model designed to ensure reduced power consumption while allowing graceful degradation in quality. The power monitor and the quality model are integrated into a programmable architecture that enables the system to proactively eliminate computations in a controlled manner that is transparent to the user. Opportunities for such proactive adaptation exist in scenarios where accuracy may not be of the utmost importance when either the battery is running low or when the channel quality is high for streaming multimedia.

We explore the power-performance trade-offs of our technique by designing power monitors for a single-precision floating point unit (FPU) and integrating them in the IDCT module of a MPEG-2 decoder. Although we consider only a 32-bit FPU as a case study, our technique is general enough to be applied to other functional units like fixed-point or reduced precision FPUs in both, application-specific and general-purpose processors. We evaluate the energy-and battery-efficiency of our approach by experimenting with different power monitor and output quality settings. Our experiments indicate that power savings up to 72% can be achieved in the IDCT module for a power monitor overhead of only 5% in the total energy. We also demonstrate that these savings are complementary to techniques like dynamic

Related Work

Low power design for multimedia systems is currently a very active field of research. In addition to circuit-level optimizations, techniques like DVS [START_REF] Lu | Reducing Multimedia Decode Power Using Feedback Control[END_REF][START_REF] Choi | Frame-based Dynamic Voltage and Frequency Scaling[END_REF][START_REF] Lu | Dynamic Frequency Scaling with Buffer Insertion for Mixed Workloads[END_REF], DPM [START_REF] Benini | Dynamic Power Management: Design Techniques and CAD Tools[END_REF] and power-aware scheduling of multimedia tasks [START_REF] Shaoxiong | Energy Reduction Techniques for multimedia applications with tolerance to deadline misses[END_REF] have also been proposed.

Architectural enhancements for multimedia processing include use of execution caches [START_REF] Azam | Low Power Data Processing by Elimination of Redundant Computations[END_REF], memoing [START_REF] Citron | Accelerating Multi-Media Processing by Implementing Memoing in Multiplication and Division Units[END_REF] and architectural adaptations for general-purpose systems [START_REF] Hughes | Saving Energy with Architectural and Frequency Adaptations for Multimedia Applications[END_REF]. Execution caches and memoing techniques take advantage of the data value locality in multimedia streams to use previously computed results that are stored in a caching structure. When the input operands exactly match those seen previously, the result from the cache is used instead of computing it. Although our technique bears some similarity to this approach, the key differences are (i) instead of a caching structure, we use a power monitor that predicts the power consumption rather than a numerical value, (ii) we relax the guarantee of accurate computation while maintaining a pre-defined output quality, (iii) we use relaxed power macro-models as monitors that have a smaller overhead than the direct-mapped caches proposed in [START_REF] Azam | Low Power Data Processing by Elimination of Redundant Computations[END_REF].

Micro-optimization of FPUs was proposed in [START_REF] Dally | Micro-optimization of Floating Point Operations[END_REF] as a method to reduce the operation count by breaking the floatingpoint operations into their constituent micro-operations and optimizing the resulting code by eliminating, combining or overlapping different micro-operations. On the other hand, our technique provides a way to turn-off the entire FPU as opposed to some micro-operations thus providing greater power savings.

Recently, DPM policies that reduce output quality to specifically target improvement in battery lifetime were proposed in [START_REF] Benini | Battery-Driven Dynamic Power Management[END_REF]. However, their method is a reactive one as it triggers a reduction in quality only after the battery voltage falls below a certain threshold. On the other hand, our method tries to proactively regulate the system power profile by using the information provided by power monitors. Our results show that such an early action approach leads to higher battery-efficiency.

Motivation

An MPEG video stream consists of a series of frames that are of three types: I-Frames (intra-coded), P-Frames (Predictivecoded) and B-frames (Bi-Directional coded). I-frames can be decoded independently while P-and B-frames require either the previous, future or both frames for decoding. Of the several steps required to decode a frame, the IDCT and Reconstruction steps are the most time-consuming and IDCT is the most computationally intensive [START_REF] Patel | Performance of a Software MPEG Video Decoder[END_REF]. The output quality of a MPEG decoder is measured objectively using the Peak-Signal-To-Noise-Ratio (PSNR), calculated with respect to reference frames at the encoder input, and subjectively using the Mean-Opinion-Score (MOS) where quality is assigned a score between 1-5 by human subjects. MOS of 4-5 represents "GOOD", 2-3 means "FAIR" and a score of 1 is "POOR" or unacceptable.

Figures 1 and2 show the relationship between the average number of computations performed by the IDCT unit per frame with the PSNR and MOS for 100 frames. Note that skipping is performed at the operation granularity rather than at frame granularity. Figure 1(b) shows that, when 88% of the computations are skipped in a P-Frame, the PSNR falls to roughly 24dB which corresponds to a MOS value of 3 (from Figure 2(b)). This indicates that the output is still of acceptable quality. This is also true of I-Frames where 55% computations can be skipped before MOS drops to 3 (Figure 1(a), 2(a)). Since the functional units are gated off when computations are skipped, this provides a power savings of 77% while maintaining acceptable quality.

A common feature of all techniques mentioned in Section 1.2 is that they guarantee accurate computation for every operation (and instruction). In our approach, we relax this guarantee and instead, intentionally introduce errors by selectively skipping computations. To prevent excessive quality degradation due to the accumulative nature of such errors over successive frames, we bind the number of skipped computations by a quality model. The proposed quality model controls the error propagation by quantifying the playback quality and using this value to direct the power monitors to either skip or execute a particular computation. The key difference between our approach and previous techniques is that instead of trading off power with a fixed, low quality level, our proposed architecture can be dynamically tuned to fit both the quality and power requirements of the system.

Methodology

Our methodology consists of three phases: (i) design of an effective power macro-model, with small area and power overhead when synthesized, to predict the power on a per-computation ba- sis, (ii) design of a quality model that quantifies the output quality of the target application and controls on/off status of the monitored units, and (iii) a programmable architecture that integrates the power monitor and the quality model to enable dynamic control of the number of computations. In what follows, we describe each phase in detail.

Macro Model Construction

The application of a power macro-model as a small synthesized circuit presents unique challenges for its design. Specifically: (i) the model should be able to track the changes in power consumption in a cycle-accurate manner with low area and power overhead, (ii) the only information available to the model is the transition activity on the inputs of the selected components, and (iii) the operation of the model should be controllable by the quality model. For design of cycle-accurate macro models, we use the approach outlined in [START_REF] Wu | Cycle-Accurate Macro-Models for RT-level Power Analysis[END_REF] in which the transitive fanout correlated input switching activity is used to construct a regression model for power estimation. However, unlike [START_REF] Wu | Cycle-Accurate Macro-Models for RT-level Power Analysis[END_REF], we assume that all the inputs in the model are uncorrelated to reduce the model complexity. Further, we use a backward elimination algorithm as opposed to the forward elimination procedure proposed in [START_REF] Wu | Cycle-Accurate Macro-Models for RT-level Power Analysis[END_REF].

The macro-model approximates the power consumption, P, as a linear function of the Hamming distance between a pair of input vectors, I c-1 and I c , in clock cycles c -1 and c respectively. The model is obtained using multiple regression over the input transition vector, in which a 1 represents a transition on the corresponding input pin. The model thus obtained is termed as the full model and contains k + 1 terms where k is equal to the number of primary inputs (PIs) of the selected component.

For large circuits, the synthesized full model results in a circuit with a large area and power overhead as compared to the monitored component itself. To reduce this overhead, we relax the full model by eliminating those terms from the full model that have the least impact on the power estimate in any given clock cycle. The relative impact of each term on the power estimate is calculated by the F * -test statistic [START_REF] Neter | Applied Linear Regression Models[END_REF] based on hypothesis testing. We use a procedure called backward elimination that starts with the full model as input and determines the level of significance of every term, obtained from the F * -distribution, for a given confidence level (95% in our case). The terms that have a F * value below some threshold are eliminated and the model is re-fitted with the remaining terms. In our case, the threshold was selected so as to sacrifice some accuracy in order to decrease the size of the macro model. The algorithm terminates when the goodness of fit, R, for the remaining terms falls below a certain value or the per-cycle estimation error, CPE [START_REF] Wu | Cycle-Accurate Macro-Models for RT-level Power Analysis[END_REF], increases above a threshold. On termination, the remaining inputs are weighted with their final F * values.

We tested the models on some large benchmark circuits and the mantissa datapaths of 32-bit floating-point multiplier and adder. We did not target the exponent datapath since their small bit-widths resulted in macro-models with excessive overhead even after relaxation. The regression coefficients were calculated using a training set of 5,000 vectors extracted from gatelevel simulation of each circuit. For complex designs with multiple components like the mantissa datapaths, gate-level simulation was performed in context of the RTL simulation of the entire FPU, as outlined in [START_REF] Bogliolo | Regression-based RTL Power Modeling[END_REF], allowing us to extract applicationspecific vectors. The fit was validated using 50,000 randomly generated vectors for the benchmark circuits and from actual MPEG-2 bitstreams for the FPU. Actual power consumption values were obtained using a gate-level power estimator. For the elimination algorithm, we selected R = 0.4 and CPE = 35% as the terminating conditions by trial-and-error.

Table 1 provides a comparison between CPE and R values for the full and relaxed models. The increase in CPE values over the full model was observed to be less than 3% while the power consumption as compared with the full model was reduced by as much as 90%. The key observation is: given a Hamming distance threshold, the relaxed models can be used to differentiate vectors that consume higher or lower power than the threshold by monitoring transitions on the selected PIs even for complex designs. We found that the false negatives and positives during this differentiation were less than 4% for all the circuits. Since the ability of the macro-model to differentiate the input vectors directly affects the output quality, we explored the effect of different macro-model sizes on the PSNR of several decoded videos. Figure 3 compares the actual measured PSNR with that obtained by skipping computations as directed by macro-models of different sizes for the FPU. Based on this, a macro-model size that yielded a prediction error of less than 3% was selected as a trade-off between prediction accuracy and area/power overhead.

Selection of a Quality Model

To prevent a runaway degradation in output quality due to error propagation over successive frames, a quality model is needed that binds the degradation in quality (PSNR/MOS in our case) with a specific number of skipped computations. Further, the model should be able to provide directives to the power monitor to guide differentiation of input vectors. In this sub-section, Previously in Figure 1, we illustrated the relationship between PSNR and the number of computations performed in the IDCT unit. Based on this observation, we constructed a regression model of the PSNR as a function of the number of computations performed. The goodness of fit, R, for the model was observed to be 0.91 for I-frames and 0.89 for P-frames respectively. Further, as explained in Section 3.1, the classification of input vectors by the macro-model is programmable by a threshold value of the Hamming distance between successive input vectors. Hence, the number of computations, and consequently the quality can be controlled by using different thresholds. We have designed such a quality model as a small look-up table (LUT) through extensive experimentation using our software prototype. Table 2 provides an example of a LUT for Pand B-frames. The first column lists the output of the model, i.e. the threshold values, as a fraction of the total Hamming distance of the monitored component. The second column lists the loss in quality, in terms of the difference in PSNR with and without skipping, when input vectors below the specified threshold were skipped. The third column lists the fraction of input vectors for which the monitored unit can be disabled and the last column lists the average MOS values for the decoded streams. The strength of this simple yet effective quality model lies in the fact that it allows the quality to degrade very slowly even for a large number of skipped computations. Further, in our experiments, we found that the computational workloads vary according to the frame types. Hence, different quality LUTs are required for I-frames and P-, B-frames. However, as will be seen in Section 3.4, the size of each table is small enough to be included in hardware with small area and power overhead.

Analysis of Power Savings

In this subsection we provide a quick analysis of the potential power savings due to the proposed architecture by using a floating-point multiplier as an example. The aim is to provide the designer with some parameters to explore the design space for the selected component and application.

The total power consumption due to the addition of a power monitor can be modeled as, where, P T represents the total power, P mon is the power overhead of the monitor circuit, P mul is the power consumed by the multiplier and R s is the skip-rate for the multiplier, defined as the fraction of time that the monitor circuit is able to disable inputs to the multiplier. Note that R s depends on the threshold value provided by the quality model and the ability of the macro-model to correctly differentiate the inputs. As we address only dynamic power consumption in this analysis, the savings in power consumption is given by,

P T = P mon + (1 -R s ) × P mul (1)
P s = [R s -(P mon /P mul )] × 100% (2)
The above equation can be used to explore the design space for both the monitor circuit and the quality model. Specifically, a quality model that allows substantial number of computations to be skipped (high R s ) for only a small quality degradation is preferable. From Table 2, it can be seen that our quality model satisfies this criteria. Similarly, a monitor circuit with a low P mon /P mul is desirable. It should be noted that these two objectives are conflicting: a smaller monitor circuit will have higher CPE which may lead to imbalances in the quality model and a restrictive quality model may result in a large monitor circuit. Hence, trade-offs can be examined depending upon the selected component and application using equation 2.

Monitor Circuit Architecture

We integrate the macro-model and quality model designs of Sections 3.1 and 3.2 into a programmable architecture for the power monitor. Figure 4 illustrates the architecture while Figure 5 shows how the monitor can be integrated in a complex system.

A bank of XOR gates is used to calculate the transition activity vector among participating bits between I c-1 and I c . The Hamming distance is then determined by a small 1's-counter circuit. The monitor can be programmed using the signals MODE, FRAME TYPE and THROTTLE. Specifically, MODE is used to select between skipping of predicted low power and high power vectors. The FRAME TYPE and THROTTLE signals are used to index the proper quality model LUTs that yield the value of THRESH. The calculated Hamming distance is compared with this value and, depending upon the MODE, the decision to skip or execute the computation is made by driving the LD DISABLE signal to the proper value. If the computation is to be skipped, then the inputs to the monitored unit are disabled to save power and previously computed outputs are maintained.

The THROTTLE signal is used to control the skip-rate by switching between different quality levels. This can be a function of one or several system parameters. In Section 4, we provide an example where this signal is derived from the sensed battery voltage. As battery voltage decreases by a certain amount, THROTTLE is used to decrease the quality to provide a graceful degradation while prolonging the battery life. The MODE signal is used to provide a fine-grained control over both the power and output quality. We consider a case where a system is under a denial-of-service power attack [START_REF] Martin | Denial-of-Service Attacks on battery-powered mobile computers[END_REF] that is trying to rapidly drain the battery. In such a case, the MODE can be set to skip all the high power vectors so as to prolong battery life as much as possible.

This simple architecture effectively integrates the macromodel and quality models to allow fine-grained architecturallevel control over the power-hungry units. The architecture can be programmed using a very few signals and consequently, can be easily integrated into a general-purpose or applicationspecific system aimed at multimedia workloads. The monitor circuit was designed in VHDL and synthesized in Synopsys using the TSMC 0.18 µm standard cell library. A 20-entry quality LUT was used with 10 entries for each frame type. The area of the resulting circuit was 8715 µm 2 while the power consumption measured with typical MPEG-2 bitstreams was 144 µW . The delay in the critical path due to addition of the monitor was 2ns. The overhead of the monitor circuit was 12% in terms of area and 5% in terms of power as compared to the FPU.

Experimental Validation

Setup: Matched software and hardware prototypes of the proposed architecture were designed in C and VHDL for singleprecision floating point multiply and add units. All bit-level hardware operations were emulated in software. Input data for power estimation was obtained from benchmark MPEG-2 streams of varying bit rates and motion characteristics. Battery lifetime estimation was performed using the PSPICE model of a Lithium-Ion battery [START_REF] Gold | A PSPICE macro-model for lithium-ion batteries[END_REF] with standard capacity 1.25 Ah and fully charged voltage of 4.1V. Battery efficiency was measured in terms of the residual battery charge at the end of a particular simulation run. Current values required for battery simulation were obtained by dividing the power profile with the rated battery voltage and were averaged over a window of 10ms to filter out effect of noise. Energy-efficiency of the approach was measured in terms of the power savings obtained by varying the threshold settings. For quality assessment of the decoded stream, PSNR was calculated using the difference in pixel values with original benchmark video sequences obtained from [START_REF]Video Traces for Network Perf. Evaluation[END_REF] and MOS values were calculated as the mean of MOS values from 5 individuals, with MOS = 3 assumed to be the minimum acceptable quality. Although, both MOS and PSNR were used as quality metrics, we report only the MOS values here due to space constraints. Energy Efficiency and QoMD Trade-Off: As a case study, we integrated a single-precision FPU with its power monitors in the IDCT module of a hardware and software MPEG-2 decoder [START_REF]MPEG Software Simulation Group[END_REF]. Instead of targeting a specific IDCT architecture, we focus on the power-hungry FPU since it can be used in either general-purpose or application-specific systems. Here, we present the results for a 32-bit FPU, but the technique is general enough to be applicable to fixed-point or reduced bit-width FPUs as well.

The software prototype was used to decode 4 benchmark videos and functional vectors to the FPU were extracted and provided to a RT-level power estimator. Figure 6 illustrates effect of skipping low power and high power vectors, using several threshold value settings, on the quality (Fig. 6(a)) and energy (Fig. 6(b)) of the decoded stream. The dotted line in Figure 6(b) represents the power savings when skipping high power vectors averaged over all the video streams and the bold lines illustrate the savings when low power vectors are skipped. Average power savings of 68.2% were observed with a gradual degradation in the quality. We observed that fewer high power vectors can be skipped since high switching activity implies more computation and consequently, a higher impact on the output quality. However, average power savings of 55% were observed as illustrated by the dotted line. Based on these experiments, we found that threshold values of 46 for P-Frames and 30 for I-frames resulted in maximum power savings of 72% for a MOS value of 3. Battery Efficiency: It has been observed that available battery charge diminishes rapidly if the current drawn from the battery is consistently higher than its rated current due to rate capacity effects [START_REF] Lahiri | Communication Architecture Based Power Management for Battery Effi cient System Design[END_REF]. Hence, in addition to energy-efficiency, a reduction in current drawn from the battery is required to prolong the battery life. Figure 7 shows a snapshot of the current profile of the baseline and modified IDCT units when (a) skipping high power vectors, and (b) skipping low power vectors. When skipping high power vectors, the current peaks are flattened resulting in a decrease in average current by 98.3%. When skipping low power vectors, current peaks are observed mainly during decoding of I-frames and the average current drawn decreases by 79.2%.

To analyze the effect of our approach on the battery life, we looped a 5000-frame video several times for a total viewing time of 1.5 hours and provided the resulting current profile to the PSPICE battery model. Typical current values due to other units involved in MPEG-2 decoding like dithering, motion estimation and display were added to the current values of the IDCT unit to simulate a realistic multimedia workload [START_REF] Chakraborty | Predicting Energy Consumption of MPEG Video Playback on Handhelds[END_REF]. The amount of charge that the battery can deliver is a function of the state-ofcharge (SOC), discharge rate and frequency of the discharge current [START_REF] Gold | A PSPICE macro-model for lithium-ion batteries[END_REF]. In [START_REF] Gold | A PSPICE macro-model for lithium-ion batteries[END_REF], the SOC is modeled as voltage across a capacitor, C CAP , where an initial voltage, V (C CAP ) = 1V corresponds to a fully charged battery (100% residual charge). At the end of the simulation run, the baseline IDCT unit resulted in a residual charge of 82% (V (C CAP ) = 0.82V ) while the residual charge due to the modified IDCT was 99.8% (V (C CAP ) = 0.998V ): an increase in battery lifetime of 1.22×.

From these experiments, we can make the following observations: (i) relaxing the guarantee of accurate computations results in significant power savings; (ii) power savings are consistent over video streams with different motion characteristics; (iii) threshold values provided by our quality model offer a simple way to dynamically control the playback quality, power consumption and discharge current; (iv) the only system-level support required for our architecture is a stimulus for changing the thresholds during program execution. Hence, our technique is orthogonal to system-level techniques like DVS and DPM and the two can be applied together to further enhance the energyefficiency. In practice, the quality levels can be decreased in response to values like the available battery SOC to prolong battery life while providing a graceful reduction in quality. Comparison with other Power Management Techniques: We compare our approach with the closed-loop policy of the batterydriven DPM system outlined in [START_REF] Benini | Battery-Driven Dynamic Power Management[END_REF] where the quality of an audio recorder is dynamically adjusted from Fine Sound to Raw Sound when the sensed battery voltage drops below a certain threshold, V th . We adapt this scheme in our prototypes for comparison using MPEG-2 streams instead of audio. The battery efficiency of [START_REF] Benini | Battery-Driven Dynamic Power Management[END_REF] depends on the amount of time for which the system can be run in Raw mode while providing a graceful quality degradation. This, in turn, depends on the length of time before the supplied voltage reaches V th . Thus the battery-efficiency of the two approaches can be compared by observing the time required for the battery voltage to drop to V th . For the experiment, we assume V th = 3.6V , which corresponds to V (C CAP ) = 0.87V in the model. The Raw quality setting is assumed to have a MOS value of 4. In our prototype, successive quality levels were selected when the sensed battery voltage reduced by 0.1V. Figure 8 illustrates that proactive computation elimination is superior both in terms of quality and battery efficiency. Specifically, our approach caused V th to be reached only after 7200sec as compared to 3690sec for the closed-loop policy resulting in a 1.95× increase in battery lifetime. Further, higher output quality can be maintained over a longer time using our approach since MOS decreases to 4 only after 7200sec. We would like to emphasize that our technique can be applied in addition to the DPM policies like Sleep and Idle states mentioned in [START_REF] Benini | Battery-Driven Dynamic Power Management[END_REF] resulting in higher battery-efficiency than these techniques.

Conclusion

In this paper, we presented a novel technique that uses dynamic, cycle-accurate power estimation of the input stream to selectively eliminate computation. We demonstrated how our approach can be used to achieve quality-driven, fine-grained control over critical, power-hungry units by using synthesized, relaxed power models as monitor circuits. Our experimental results with the IDCT unit of a MPEG-2 decoder indicate that this approach can successfully exploit the error tolerance of certain applications and dynamically regulate the application power profile to achieve energy-and battery-efficient operation.

Figure 1 .

 1 Figure 1. Effect of computation skipping on PSNR and Power (a) I-Frames, (b) P-Frames

Figure 2 .

 2 Figure 2. Effect of computation skipping on MOS (a) I-Frames, (b) P-Frames

Figure 3 .

 3 Figure 3. Prediction Error vs. Macro Model size

Figure 4 .

 4 Figure 4. Power Monitor Architecture we outline the design of such a model with MPEG-2 decoding as the target application.Previously in Figure1, we illustrated the relationship between PSNR and the number of computations performed in the IDCT unit. Based on this observation, we constructed a regression model of the PSNR as a function of the number of computations performed. The goodness of fit, R, for the model was observed to be 0.91 for I-frames and 0.89 for P-frames respectively. Further, as explained in Section 3.1, the classification of input vectors by the macro-model is programmable by a threshold value of the Hamming distance between successive input vectors. Hence, the number of computations, and consequently the quality can be controlled by using different thresholds.

Figure 5 .

 5 Figure 5. System Model with Power Monitor

Figure 6 .

 6 Figure 6. Energy-Performance Trade-Off

Figure 7 .

 7 Figure 7. Discharge Current when skipping -(a) high power vectors, (b) low power vectors

Figure 8 .

 8 Figure 8. Comparison of trade-off characteristics with Battery-Driven DPM [5]

Table 1 . Comparison of Full and Relaxed Models of the Power Monitors

 1

		Full Model		Relaxed Model
	Circuit	No. of	CPE	R	No. of	CPE	R	Power
		Terms	(%)		Terms	(%)		Savings(%)
	c2670	233	14.37 0.69	16	15.13 0.65	90.34
	c5315	178	9.84	0.81	16	11.31 0.73	87.60
	c7552	207	10.32 0.94	16	10.86 0.93	89.23
	FP Mult	50	17.76 0.47	20	18.26 0.44	45.47
	FP Add	58	29.21 0.89	28	31.70 0.88	52.65

Table 2 . Quality Model for FP MULT: P-Frames

 2

	Threshold	PSNR	Computations MOS
	(%)	Difference(dB)	Skipped(%)
	10	0.62	15.4	5
	20	0.64	26.6	5
	30	0.92	41.5	5
	40	2.85	72.5	4
	50	5.84	92.3	3

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)

* supported in part by NSF under grants 0219801


Fausto Galetto
email: fausto.galetto@gmail.com

Independent Researcher

RIEMANN'S HYPOTHESIS and the LIOUVILLE FUNCTION for THE PROOF OF RH Another case that I SEE IT, BUT I CAN'T BELIEVE IT

Keywords: RH (the Riemann hypothesis), (s) (the Riemann zeta function), integral equations, the Liouville function

It is well known that "The Riemann hypothesis is equivalent to the statement that for every  > 0 the function L(x)/x 1/2+ approaches zero as x ", where L is the "cumulative" Liouville function.

Starting from the definitions of L(x) and (s) we derive an integral equation about L(x): from that we derive that |L(x)|<x 1/2+ ; the proof of the Riemann hypothesis follows.

Introduction

Riemann devised the Riemann zeta function: (z), where z is a complex number z=x+iy and i is the "positive" imaginary unit such that i 2 =-1. The Riemann Hypothesis states all the nontrivial zeros are the complex numbers z=1/2 + iy, with suitable values of y [the line z=1/2 + iy in the z plane is named Critical Line]. All the "known" zeros computed up to now [up to 2018], more than 10 12 zeros have been computed, all on the Critical Line. Many people tried to prove RH and making it a theorem; the author himself, using the theory of Hilbert Spaces, tried it [START_REF] Galetto | Riemann Hypothesis proved[END_REF] after studying the book of Titchmarsh [START_REF] Titchmarsh | The Theory of the Riemann Zeta-Function[END_REF]; there one finds that the Riemann hypothesis is equivalent to the statement that for every  > 0 the Mertens function M(x)=O(x 1/2+ ): using this equivalence the author provided [3] a new proof of RH. Now the author suggest another new proof of RH, by using the fact that the Riemann hypothesis is equivalent to the statement that for every  > 0 the "cumulative" Liouville function L(x)=O(x 1/2+ ).

Let n be a positive integer; we find the prime factors of n and count them: we indicate as (n) the number of prime factors of n, counted with their multiplicity.

The Liouville function is defined by 

It takes only two values -1 and 1; it graph is an infinite "rectangular" wave, with steps up and down according the number (n).

It is a sequence like {1,-1,-1, 1,-1, 1,-1,-1, 1, 1,-1,-1,-1, 1, 1, 1,-1,-1,-1,-1, 1, ..., 1,..., -1, ..., ..., ...}. which is a "determination" of a random walk. The "cumulative" function of Liouville is defined by the sum where and n being integer numbers. For x, a real number, the cumulative Liouville function is defined by the sum [START_REF] Titchmarsh | The Theory of the Riemann Zeta-Function[END_REF] The Riemann Hypothesis is equivalent to the statement that, for every fixed > 0, (2)

Connections between L(x) and (s)

In this section we use the standard symbols for the Riemann zeta function (s); s is the complex variable, s=+it; x is a real variable. Since (3) from ( 3) one can prove that, for >1

On the other hand one can prove that [START_REF] Galetto | Reliability and Maintenance, Scientific Methods, Practical Approach[END_REF] From ( 4) and ( 5), without assuming that RH is true, we derive the integral equation (6)

We will prove it after the introduction to the Theory of Distributions (next section).

Theory of Distributions Basics

Distribution theory [START_REF] Amerio | Analisi Matematica[END_REF] can be thought of as the completion of differential calculus, because in the theory any distribution can be differentiated any times we want (it is one of the two great revolutions in mathematical analysis in the 20th century).

It is known what a function f(x), with x real, is. The same for f(s), with s complex. We can generalise the definition of a function f(x) by computing the integral (7)

The functions (x) are named test functions and are vanishing outside a bounded subset of the space R and are such that all partial derivatives of all orders of (x) are continuous. [for the case "monodimensional"!] The integral is to be intended in terms of Lebesgue integration theory. Any function gives rise to a distribution by setting , at least if the integral can be defined. This is certainly true if f is continuous, but actually more general functions will work. The so called "Dirac -function" actually is defined only as a distribution by <,>=(0). It cannot differentiated as a function, but it can differentiated as a distribution by <,>=-(0).

In the real space R we can define the Heaviside function H(x) [also named step function] which is H(x) cannot be differentiated at x=0. On the contrary, the distribution <H,> can be differentiated and we have <H,>=<,>: we indicate it with the symbol (x). There is a second type of step function, actually distribution, named as well Heaviside function H(x) which is The derivative of this distribution is <H,>=<,>=1/2(x) For distributions we can define all the operations (and others) we can define for functions: e.g. Fourier transforms, Laplace transforms, integration, derivation, .... In the next sections we will consider the Mertens function, in the sense of the Distribution Theory, in order to take advantage of the Theory.

The integral equation for L(x)

Inserting ( 4) into ( 5) we get [without assuming that RH is true] (8) Some manipulations of (8) give (9) and finally (10) To prove (8) we need to consider first the integral, where x and y are real variables, and s the complex variable, s=+it Integrating, when x<y, one gets 0; integrating, when x=y, one gets ½; integrating, when x>y, one gets 1. This is the second type of step distribution, H(u-1) with u=x/y; when x=y H(u-1)=H(0). The complex integral in (9) then is related to the distribution which is 0 for any u1.

That means that the integral about the "integration variable y" must be 0 above x. Therefore we get (10). L(x) is the distribution related to the Liouville function. This is the point given in the title:

I SEE IT, BUT I CAN'T BELIEVE IT

Let's look at (10) in terms of a random walk, ruled by tossing a fair coin every 1 second; after each toss the function L(y) takes a step "upwards" if heads shows, "downwards" if tails shows; L(y) is the value of the height of a staircase, at time y: the ratio L(y)/y is the rate of height-change in the interval 0 ----y. Formula (10) tells us the L(x) is related to the rate of height-change L(y)/y. If we let S n be the random variable "sum of the sequence of Heads=1 and Tails=-1" we have that (Central Limit Theorem in reference [START_REF] Galetto | Reliability and Maintenance, Scientific Methods, Practical Approach[END_REF])

proving that all random walks of the type considered are governed by the same probabilities for large n: the same is for the numbers (n), which are one of the possible paths of a random walk, ruled by tossing a fair coin. By choosing x=n /2 we get that is it is with probability 1.

The integral inequality for the absolute value |L(x)|

In order to prove the Riemann Hypothesis RH, we must find the distribution |L(x)| related to the integral equation (10).

For the absolute value we have, being >0,

Let's put g(t)=|L(t)|, considered as a distribution, and find its Laplace transform (p is the complex variable)

Then Therefore If we seek a solution with  >0

we get that is (12)

By choosing =3/2 we have -1<1/2+, that is t 1/2+ as solution of the integral inequality (9), and eventually (13)

Conclusion

Since we know that "The Riemann hypothesis is equivalent to the statement that for every  > 0 the function L(x)=O(x 1/2+ )", where L is the "cumulative" Liouville function and we found that |L(x)|<x 1/2+ is the solution of the integral inequality about |L(x)| [derived from integral equation about L(x), found from L(x) and (2s)/(s)], the proof of the Riemann hypothesis is proved. (see also [START_REF] Galetto | Riemann Hypothesis proved[END_REF]3]). It is catching the probabilistic interpretation of L(x), even though the "cumulative" Liouville function is not random...