CAD of Circuits and Integrated Systems

Ali Mahdoum

• Publisher: Wiley-ISTE
• Year: 2020
• ISBN:
  9781119751588
• Edition: 1
• Topic: Technology & Engineering
• Subtopic: Electrical Engineering & Telecommunications
• Index: Technology & Engineering

This book addresses the difficulty of obtaining a quality solution, that is, pre optimal or even optimal, in a reasonable time from a central processing unit (CPU). As polynomial problems can be treated by exact methods, the problem posed concerns non-polynomial problems, for which it is necessary to develop efficient algorithms based on heuristics or meta-heuristics. Chapter 3 of this book demonstrates how to develop such algorithms, which are characterized by: an initialization of argued solutions (sometimes, the global optimum can be obtained from such an initialization); a non-random generation of solutions (to avoid generating the same solution several times, or even generating solutions that cannot be achieved); avoidance of being trapped by a local optimum; good use of CPU time by reducing the size of the space of solutions to be explored (which is often very large for such problems) without compromising the quality of the solution; plus a reasoned displacement from one solution to another, to improve the quality of the solution as the processing is carried out. These aspects are applied to concrete applications in the design of integrated circuits and systems at various levels. To do this and to help the reader better understand this problem, Chapters 1 and 2 present basic notions on computational complexity, and the design of integrated circuits and systems.

1
Basic Notions on Computational Complexity and Approximate Techniques

1.1. Computational complexity

1.1.1. Introduction

The execution time of a program depends on several factors:

• – program data: for example, sorting about 10 numbers requires less execution time than sorting out millions of numbers;
• – quality of the code generated by the compiler: codes generated by programming languages do not all have the same quality (this is the case of C, C++ and Java: if the application is not object-oriented and will be executed on some platform (operating system, processor frequency, memory size, etc.), then it is better to implement it in C, which generates a “lighter” code);
• – computational complexity: this metric gives the developer an idea of the execution time of their program, independently of programming language and platform (processor, memory capacity, etc.). Computational complexity is therefore an important concept, all the more so as it offers the developer an indication on whether their program takes a reasonable CPU time to reach results, even when significant resources (processor frequency, memory capacity) are at their disposal. In other terms, it may signal to the designer the need to modify their algorithm, if it takes an “infinite” time to reach results.

1.1.2. Big O notation

DEFINITION.– Computational complexity T(n) is O(f(n)) if there are constants c and n₀ such that: T(n) ≤ c * f(n) ∀ n ≥ n₀; c > 0; n₀ ≥ 0

EXAMPLE 1.1.– T(n) = (n+1)²

T(n) is O(n²). Indeed, T(n) ≤ 4 * n² ∀ n ≥ 1 (c = 4; n₀ = 1)

We will subsequently see how the function T(n), associated with a given algorithm, can be determined.

EXAMPLE 1.2.– Consider T(n) = n²+n. Is it possible to consider that T(n) is O(n)?

If yes, we would have: n²+n ≤ c * n ⇔ n²+n(1-c) ≤ 0 ⇔ n(n+1-c) ≤ 0

Since n ≥ 0, we would have: c ≥ n+1 ⇒ c is not a constant and therefore T(n) is not O(n).

1.1.2.1. Sum

If T₁(n) is O(f(n)) and T₂(n) is O(g(n)), then T₁(n) + T₂(n) is O(max(f(n),g(n)))

PROOF.–

T₁(n) is O(f(n)) ⇔ ∃ c₁ > 0, n₁ ≥ 0: T₁(n) ≤ c₁ f(n) ∀ n ≥ n₁

⇒ T₁(n) ≤ c₁ max(f(n), g(n)) ∀ n ≥ n₁

T₂(n) is O(g(n)) ⇔ ∃ c₂ > 0, n₂ ≥ 0: T₂(n) ≤ c₂ g(n) ∀ n ≥ n₂

⇒ T₂(n) ≤ c₂ max(f(n), g(n)) ∀ n ≥ n₂

⇒ T₁(n) + T₂(n) ≤ (c₁ + c₂) max(f(n),g(n)) ∀ n ≥ max(n₁, n₂)

Generally speaking, if T_i(n) ≤ c_i f_i (n) ∀ n ≥ n_i; i=1, 2, ……., p, then:

NOTE.–

Consider T(n)=n²+n

It can be said that T(n) is:

- O(n²+n) as T(n) ≤ 1 * (n²+n) ∀ n ≥ 0;

C=max(c₁, c₂)=1; f₁(n)+f₂(n)=n²+n;

- O(n²) as T(n) ≤ 2 * n² ∀ n ≥ 0;

C=c₁+c₂=1+1=2; max(n², n) = n²

1.1.2.2. Product

If T₁(n) is O(f(n)) and T₂(n) is O(g(n)), then T₁(n)* T₂(n) is O(f(n)*g(n))

PROOF.–

T₁(n) is O(f(n)) ⇔ ∃ c₁ > 0, n₁ ≥ 0: T₁(n) ≤ c₁ f(n) ∀ n ≥ n₁

T₂(n) is O(g(n)) ⇔ ∃ c₂ > 0, n₂ ≥ 0: T₂(n) ≤ c₂ g(n) ∀ n ≥ n₂

⇒ T₁(n)* T₂(n) ≤ (c₁ * c₂) f(n) * g(n) ∀ n ≥ max (n₁, n₂) ⇒ T₁(n) * T₂(n) is O(f(n) *g(n))

Generally speaking, if T_i(n) ≤ c_i f_i(n) ∀ n ≥ n_i; i=1, 2, ……., p, then:

which means

1.1.3. Ω Notation

DEFINITION.– Computational complexity T(n) is Ω(g(n)) if there are constants c and n₀ such that: T(n) ≥ c * g(n) ∀ n ≥ n₀; c > 0; n₀ ≥ 0

EXAMPLE 1.3.– T(n) = n²+n. It can be verified that T(n) is Ω(n) due to...

Table of contents

• Cover
• Table of Contents
• Preface
• 1 Basic Notions on Computational Complexity and Approximate Techniques
• 2 Basic Notions on the Design of Digital Circuits and Systems
• 3 Case Study: Application of Heuristics and Metaheuristics in the Design of Integrated Circuits and Systems
• References
• Index
• End User License Agreement