Computer as Components
`s
`Principles of Embedded
`Computing System Design
`
`Third Edition
`
`Marilyn Wolf
`
`AMSTERDAM • BOSTON • HEIDELBERG • LONDON
`NEW YORK • OXFORD • PARIS • SAN DIEGO
`SAN FRANCISCO • SINGAPORE • SYDNEY • TOKYO
`
`Morgan Kaufman is an imprint of Elsevier
`
`SAMSUNG ELECTRONICS CO., LTD., v. AFFINITY LABS OF TEXAS, LLC
`IPR2014-01181 EXHIBIT 2028 – 1
`
`

`

`Acquiring Editor: Todd Green
`Development Editor: Nate McFadden
`Project Manager: Andre Cuello
`Designer: Mark Rodgers
`
`Morgan Kaufmann is an imprint of Elsevier
`225 Wyman Street, Waltham, MA 02451, USA
`
`© 2012 Elsevier, Inc. All rights reserved.
`
`Designations used by companies to distinguish their products are often claimed as trademarks or registered trademarks.
`In all instances in which Morgan Kaufmann Publishers is aware of a claim, the product names appear in initial capital or
`all capital letters. Readers, however, should contact the appropriate companies for more complete information regarding
`trademarks and registration.
`
`No part of this publication may be reproduced or transmitted in any form or by any means, electronic or mechanical,
`including photocopying, recording, or any information storage and retrieval system, without permission in writing from
`the publisher. Details on how to seek permission, further information about the Publisher’s permissions policies and our
`arrangements with organizations such as the Copyright Clearance Center and the Copyright Licensing Agency, can be
`found at our website: www.elsevier.com/permissions.
`
`This book and the individual contributions contained in it are protected under copyright by the Publisher (other than as
`may be noted herein).
`
`Notices
`Knowledge and best practice in this field are constantly changing. As new research and experience broaden our
`understanding, changes in research methods or professional practices, may become necessary.
`
`Practitioners and researchers must always rely on their own experience and knowledge in evaluating and using any
`information or methods described herein. In using such information or methods they should be mindful of their own
`safety and the safety of others, including parties for whom they have a professional responsibility.
`
`To the fullest extent of the law, neither the Publisher nor the authors, contributors, or editors, assume any liability for any
`injury and/or damage to persons or property as a matter of products liability, negligence or otherwise, or from any use or
`operation of any methods, products, instructions, or ideas contained in the material herein.
`
`Library of Congress Cataloging-in-Publication Data
`Application submitted.
`
`British Library Cataloguing-in-Publication Data
`A catalogue record for this book is available from the British Library.
`
`ISBN: 978-0-12-388436-7
`
`For information on all MK publications
`visit our website at www.mkp.com
`
`Printed in the United States of America
`
`12 13 14 10 9 8 7 6 5 4 3 2 1
`
`Typeset by diacriTech, India
`
`SAMSUNG ELECTRONICS CO., LTD., v. AFFINITY LABS OF TEXAS, LLC
`IPR2014-01181 EXHIBIT 2028 – 2
`
`

`

`Program Design and
`Analysis
`
`CHAPTER
`
`5
`
`CHAPTER POINTS
`• Some useful components for embedded software.
`• Models of programs, such as data flow and control flow graphs.
`• An introduction to compilation methods.
`• Analyzing and optimizing programs for performance, size, and power consumption.
`• How to test programs to verify their correctness.
`• Design examples: Software modem, digital still camera.
`
`5.1 Introduction
`In this chapter we study in detail the process of creating programs for embedded
`processors. The creation of embedded programs is at the heart of embedded system
`design. If you are reading this book, you almost certainly have an understanding of
`programming, but designing and implementing embedded programs is different and
`more challenging than writing typical workstation or PC programs. Embedded code
`must not only provide rich functionality, it must also often run at a required rate to
`meet system deadlines, fit into the allowed amount of memory, and meet power con-
`sumption requirements. Designing code that simultaneously meets multiple design
`constraints is a considerable challenge, but luckily there are techniques and tools that
`we can use to help us through the design process. Making sure that the program works
`is also a challenge, but once again methods and tools come to our aid.
`Throughout the discussion we concentrate on high-level programming languages,
`specifically C. High-level languages were once shunned as too inefficient for embed-
`ded microcontrollers, but better compilers, more compiler-friendly architectures, and
`faster processors and memory have made high-level language programs common.
`Some sections of a program may still need to be written in assembly language if the
`compiler doesn’t give sufficiently good results, but even when coding in assembly
`language it is often helpful to think about the program’s functionality in high-level
`form. Many of the analysis and optimization techniques that we study in this chapter
`are equally applicable to programs written in assembly language.
`
`
`Computer as Components. s DOI: 10.1016/B978-0-12-388436-7.00005-2
`
`© 2012 Elsevier, Inc. All rights reserved.
`
`213
`
`SAMSUNG ELECTRONICS CO., LTD., v. AFFINITY LABS OF TEXAS, LLC
`IPR2014-01181 EXHIBIT 2028 – 3
`
`

`

`214
`
`CHAPTER 5 Program Design and Analysis
`
`State machine style
`
`The next section talks about some software components that are commonly used in
`embedded software. Section 5.3 introduces the control/data flow graph as a model for
`high-level language programs (which can also be applied to programs written origi-
`nally in assembly language). Section 5.4 reviews the assembly and linking process
`while Section 5.5 introduces some compilation techniques. Section 5.6 introduces
`methods for analyzing the performance of programs. We talk about optimization tech-
`niques specific to embedded computing in the next three sections: performance in Sec-
`tion 5.7, energy consumption in Section 5.8, and size in Section 5.9. In Section 5.10,
`we discuss techniques for ensuring that the programs you write are correct. We close
`with two design examples: a software modem as a design example in Section 5.11 and
`a digital still camera in Section 5.12.
`
`5.2 Components for embedded programs
`In this section, we consider code for three structures or components that are com-
`monly used in embedded software: the state machine, the circular buffer, and the
`queue. State machines are well suited to reactive systems such as user interfaces;
`circular buffers and queues are useful in digital signal processing.
`
`5.2.1 State machines
`When inputs appear intermittently rather than as periodic samples, it is often conve-
`nient to think of the system as reacting to those inputs. The reaction of most systems
`can be characterized in terms of the input received and the current state of the system.
`This leads naturally to a finite-state machine style of describing the reactive system’s
`behavior. Moreover, if the behavior is specified in that way, it is natural to write the
`program implementing that behavior in a state machine style. The state machine style
`of programming is also an efficient implementation of such computations. Finite-state
`machines are usually first encountered in the context of hardware design.
`Programming Example 5.1 shows how to write a finite-state machine in a high-
`level programming language.
`
`Programming Example 5.1 A State Machine in C
`The behavior we want to implement is a simple seat belt controller [Chi94]. The control-
`ler’s job is to turn on a buzzer if a person sits in a seat and does not fasten the seat belt
`within a fixed amount of time. This system has three inputs and one output. The inputs are
`a sensor for the seat to know when a person has sat down, a seat belt sensor that tells when
`the belt is fastened, and a timer that goes off when the required time interval has elapsed.
`The output is the buzzer. Appearing below is a state diagram that describes the seat belt
`controller’s behavior.
`The idle state is in force when there is no person in the seat. When the person sits down,
`the machine goes into the seated state and turns on the timer. If the timer goes off before the
`seat belt is fastened, the machine goes into the buzzer state. If the seat belt goes on first,
`it enters the belted state. When the person leaves the seat, the machine goes back to idle.
`
`SAMSUNG ELECTRONICS CO., LTD., v. AFFINITY LABS OF TEXAS, LLC
`IPR2014-01181 EXHIBIT 2028 – 4
`
`

`

`5.2 Components for embedded programs
`
`215
`
`Inputs/outputs
`(⫺ ⫽ no action)
`
`No seat/
`buzzer off
`
`No seat/–
`
`Idle
`
`No seat/–
`
`Seat/timer on
`
`Buzzer
`
`Timer/buzzer on
`
`Seated
`
`No belt
`and no
`timer/–
`
`Belt/
`buzzer off
`
`Belt/–
`
`Belted
`
`No belt/timer on
`
`To write this behavior in C, we will assume that we have loaded the current values of all
`three inputs (seat, belt, timer) into variables and will similarly hold the outputs in vari-
`ables temporarily (timer_on, buzzer_on). We will use a variable named state to hold
`the current state of the machine and a switch statement to determine what action to take in
`each state. Here is the code:
`
`#define IDLE 0
`#define SEATED 1
`#define BELTED 2
`#define BUZZER 3
`switch(state) { /* check the current state */
`case IDLE:
`if (seat){ state = SEATED; timer_on = TRUE; }
`/* default case is self-loop */
`break;
`case SEATED:
`if (belt) state = BELTED; /* won’t hear the buzzer */
`else if (timer) state = BUZZER; /* didn’t put on
`belt in time */
`/* default case is self-loop */
`break;
`case BELTED:
`if (!seat) state = IDLE; /* person left */
`else if (!belt) state = SEATED; /* person still
`
`in seat */
`
`buzzer */
`
`break;
`case BUZZER:
`if (belt) state = BELTED; /* belt is on---turn off
`
`else if (!seat) state = IDLE; /* no one in seat--
`turn off buzzer */
`break;
`
`}
`
`This code takes advantage of the fact that the state will remain the same unless explicitly
`changed; this makes self-loops back to the same state easy to implement. This state machine
`may be executed forever in a while(TRUE) loop or periodically called by some other code.
`In either case, the code must be executed regularly so that it can check on the current value
`of the inputs and, if necessary, go into a new state.
`
`SAMSUNG ELECTRONICS CO., LTD., v. AFFINITY LABS OF TEXAS, LLC
`IPR2014-01181 EXHIBIT 2028 – 5
`
`

`

`216
`
`CHAPTER 5 Program Design and Analysis
`
`Data stream style
`
`Circular buffer
`
`Instruction set support
`
`5.2.2 Circular buffers and stream-oriented programming
`The data stream style makes sense for data that comes in regularly and must be processed
`on the fly. The FIR filter of Application Example 2.1 is a classic example of stream-
`oriented processing. For each sample, the filter must emit one output that depends on
`the values of the last n inputs. In a typical workstation application, we would process
`the samples over a given interval by reading them all in from a file and then comput-
`ing the results all at once in a batch process. In an embedded system we must not only
`emit outputs in real time, but we must also do so using a minimum amount of memory.
`The circular buffer is a data structure that lets us handle streaming data in an efficient
`way. Figure 5.1 illustrates how a circular buffer stores a subset of the data stream. At each
`point in time, the algorithm needs a subset of the data stream that forms a window into
`the stream. The window slides with time as we throw out old values no longer needed and
`add new values. Because the size of the window does not change, we can use a fixed-size
`buffer to hold the current data. To avoid constantly copying data within the buffer, we will
`move the head of the buffer in time. The buffer points to the location at which the next
`sample will be placed; every time we add a sample, we automatically overwrite the oldest
`sample, which is the one that needs to be thrown out. When the pointer gets to the end of
`the buffer, it wraps around to the top.
`Many DSPs provide addressing modes to support circular buffers. For example, the
`C55x [Tex04] provides five circular buffer start address registers (their names start with
`BSA). These registers allow circular buffers to be placed without alignment constraints.
`
`Time t
`
`Time
`
`1
`
`2
`
`3
`
`4
`
`5
`
`6
`
`5 2 3 4
`
`Time t ⫹ 1
`
`Data stream
`
`1 2 3 4
`
`Time t
`
`Time t ⫹ 1
`Circular buffer
`
`FIGURE 5.1
`A circular buffer.
`
`SAMSUNG ELECTRONICS CO., LTD., v. AFFINITY LABS OF TEXAS, LLC
`IPR2014-01181 EXHIBIT 2028 – 6
`
`

`

`5.2 Components for embedded programs
`
`217
`
`High-level language
`implementation
`
`In the absence of specialized instructions, we can write our own C code for a circu-
`lar buffer. This code also helps us understand the operation of the buffer. Programming
`Example 5.2 provides an efficient implementation of a circular buffer.
`
`Programming Example 5.2 A Circular Buffer in C
`Once we build a circular buffer, we can use it in a variety of ways. We will use an array as
`the buffer:
`
`#define CMAX 6 /* filter order */
`
`int circ[CMAX]; /* circular buffer */
`int pos; /* position of current sample */
`
`The variable pos holds the position of the current sample. As we add new values to the
`buffer this variable moves.
`Here is the function that adds a new value to the buffer:
`
`void circ_update(int xnew) {
`
`/* add the new sample and push off the oldest one */
`
`/* compute the new head value with wraparound; the pos
`
`pointer moves from 0 to CMAX-1 */
`
`pos = ((pos == CMAX-1) ? 0 : (pos+1));
`
`/* insert the new value at the new head */
`
`circ[pos] = xnew;
`
`}
`
`The assignment to pos takes care of wraparound—when pos hits the end of the array it
`returns to zero. We then put the new value into the buffer at the new position. This overwrites
`the old value that was there. Note that as we go to higher index values in the array we march
`through the older values.
`We can now write an initialization function. It sets the buffer values to zero. More impor-
`tant, it sets pos to the initial value. For ease of debugging, we want the first data element to
`go into circ[0]. To do this, we set pos to the end of the array so that it is set to zero before
`the first element is added:
`
`void circ_init() {
`
`int i;
`
`for (i=0; i<CMAX; i++) /* set values to 0 */
`
`
`circ[i] = 0;
`
`
` pos=CMAX-1; /* start at tail so first element will be at 0 */
` }
`
`We can also make use of a function to get the ith value of the buffer. This function has
`to translate the index in temporal order—zero being the newest value—to its position in the
`array:
`
`int circ_get(int i) {
`
`/* get the ith value from the circular buffer */
`
`int ii;
`
`SAMSUNG ELECTRONICS CO., LTD., v. AFFINITY LABS OF TEXAS, LLC
`IPR2014-01181 EXHIBIT 2028 – 7
`
`

`

`218
`
`CHAPTER 5 Program Design and Analysis
`
`Signal flow graph
`
`Filters and buffering
`
`
`
`
`
`
`
`
`/* compute the buffer position */
`ii = (pos - i) % CMAX;
`/* return the value */
`return circ[ii];
`}
`
`We are now in a position to write C code for a digital filter. To help us understand
`the filter algorithm, we can introduce a widely used representation for filter functions.
`The FIR filter is only one type of digital filter. We can represent many differ-
`ent filtering structures using a signal flow graph as shown in Figure 5.2. The filter
`operates at a sample rate with inputs arriving and outputs generated at the sample
`rate. The inputs x[n] and y[n] are sequences indexed by n, which corresponds to the
`sequence of samples. Nodes in the graph can represent either arithmetic operators or
`delay operators. The + node adds its two inputs and produces the output y[n]. The
`box labeled z-1 is a delay operator. The z notation comes from the z transform used
`in digital signal processing; the -1 superscript means that the operation performs a
`time delay of one sample period. The edge from the delay operator to the addition
`operator is labeled with b1, meaning that the output of the delay operator is multi-
`plied by b1.
`The code to produce one FIR filter output looks like this:
`
`for (i=0, y=0.0; i<N; i++)
`y += x[i] * b[i];
`
`However, the filter takes in a new sample on every sample period. The new input
`becomes x1, the old x1 becomes x2, etc. x0 is stored directly in the circular buffer but
`must be multiplied by b0 before being added to the output sum. Early digital filters
`were built-in hardware, where we can build a shift register to perform this operation. If
`we used an analogous operation in software, we would move every value in the filter
`on every sample period. We can avoid that with a circular buffer, moving the head
`without moving the data elements.
`
`x(n)
`
`⫹
`
`y(n)
`
`z⫺1
`
`b1
`
`FIGURE 5.2
`A signal flow graph.
`
`SAMSUNG ELECTRONICS CO., LTD., v. AFFINITY LABS OF TEXAS, LLC
`IPR2014-01181 EXHIBIT 2028 – 8
`
`

`

`5.2 Components for embedded programs
`
`219
`
`The next example uses our circular buffer class to build an FIR filter.
`
`Programming Example 5.3 An FIR Filter in C
`Here is a signal flow graph for an FIR filter:
`
`x(n)
`
`x0
`
`b0
`
`⫹
`
`y(n)
`
`z⫺1
`
`x1
`
`z⫺1
`
`x2
`
`z⫺1
`
`x3
`
`b1
`
`b2
`
`b3
`
`⫹
`
`⫹
`
`⫹
`
`The delay elements running vertically hold the input samples with the most recent sam-
`ple at the top and the oldest one at the bottom. Unfortunately, the signal flow graph doesn’t
`explicitly label all of the values that we use as inputs to operations, so the figure also shows
`the values (xi) we need to operate on in our FIR loop.
`When we compute the filter function, we want to match the bi’s and xi’s. We will use our
`circular buffer for the x’s, which change over time. We will use a standard array for the b’s,
`which don’t change. In order for the filter function to be able to use the same I value for
`both sets of data, we need to put the x data in the proper order. We can put the b data in a
`standard array with b0 being the first element. When we add a new x value, it becomes x 0
`and replaces the oldest data value in the buffer. This means that the buffer head moves from
`higher to lower values, not lower to higher as we might expect.
`Here is the modified version of circ_update() that puts a new sample into the buffer
`into the desired order:
`
`void circ_update(int xnew) {
`
`/* add the new sample and push off the oldest one */
`
`/* compute the new head value with wraparound; the pos
`pointer moves from CMAX-1 down to 0 */
`pos = ((pos == 0) ? CMAX-1 : (pos-1));
`/* insert the new value at the new head */
`circ[pos] = xnew;
`}
`
`
`
`
`
`
`SAMSUNG ELECTRONICS CO., LTD., v. AFFINITY LABS OF TEXAS, LLC
`IPR2014-01181 EXHIBIT 2028 – 9
`
`

`

`220
`
`CHAPTER 5 Program Design and Analysis
`
`We also need to change circ_init() to set pos = 0 initially. We don’t need to change
`circ_get();
`Given these functions, the filter itself is simple. Here is our code for the FIR filter
`function:
`
`int fir(int xnew) {
`
`/* given a new sample value, update the queue and compute the
`filter output */
`int i;
`
`int result; /* holds the filter output */
`
`circ_update(xnew); /* put the new value in */
`for (i=0, result=0; i<CMAX; i++) /* compute the filter
`
`function */
`result += b[i] * circ_get(i);
`return result;
`}
`
`
`
`
`
`
`
`
`
`
`
`
`There is only one major structure for FIR filters but several for IIR filters, depend-
`ing on the application requirements. One of the important reasons for so many dif-
`ferent IIR forms is numerical properties—depending on the filter structure and
`coefficients, one structure may give significantly less numerical noise than another.
`But numerical noise is beyond the scope of our discussion so let’s concentrate on
`one form of IIR filter that highlights buffering issues. The next example looks at one
`form of IIR filter.
`
`Programming Example 5.4 A Direct Form II IIR Filter Class in C
`Here is what is known as the direct form II of an IIR filter:
`
`x(n)
`
`⫹
`
`v0
`
`b0
`
`z⫺1
`
`⫺a1
`
`v1
`
`b1
`
`⫹
`
`z⫺1
`v2
`
`z⫺1
`v3
`
`b2
`
`b3
`
`⫺a2
`
`⫹
`
`⫺a3
`
`⫹
`
`y(n)
`
`⫹
`
`⫹
`
`⫹
`
`⫹
`
`SAMSUNG ELECTRONICS CO., LTD., v. AFFINITY LABS OF TEXAS, LLC
`IPR2014-01181 EXHIBIT 2028 – 10
`
`

`

`5.2 Components for embedded programs
`
`221
`
`This structure is designed to minimize the amount of buffer space required. Other forms of
`the IIR filter have other advantages but require more storage. We will store the vi values as in
`the FIR filter. In this case, v0 does not represent the input, but rather the left-hand sum. But
`v0 is stored before multiplication by b0 so that we can move v0 to v1 on the following sample
`period.
`We can use the same circ_update() and circ_get() functions that we used for the
`FIR filter. We need two coefficient arrays, one for as and one for bs; as with the FIR filter,
`we can use standard C arrays for the coefficients because they don’t change over time. Here
`is the IIR filter function:
`
`int iir2(int xnew) {
`
`/* given a new sample value, update the queue and compute
`the filter output */
`int i, aside, bside, result;
`
`for (i=0, aside=0; i<ZMAX; i++)
`
` aside += -a[i+1] * circ_get(i);
`for (i=0, bside=0; i<ZMAX; i++)
`
` bside += b[i+1] * circ_get(i);
`result = b[0] * (xnew + aside) + bside;
`circ_update(xnew); /* put the new value in */
`return result;
`}
`
`
`
`
`
`
`
`
`
`
`
`
`
`5.2.3 Queues and producer/consumer systems
`Queues are also used in signal processing and event processing. Queues are used
`whenever data may arrive and depart at somewhat unpredictable times or when vari-
`able amounts of data may arrive. A queue is often referred to as an elastic buffer. We
`saw how to use elastic buffers for I/O in Chapter 3.
`One way to build a queue is with a linked list. This approach allows the queue to
`grow to an arbitrary size. But in many applications we are unwilling to pay the price of
`dynamically allocating memory. Another way to design the queue is to use an array to
`hold all the data. Although some writers use both circular buffer and queue to mean the
`same thing, we use the term circular buffer to refer to a buffer that always has a fixed
`number of data elements while a queue may have varying numbers of elements in it.
`Programming Example 5.5 gives C code for a queue that is built from an array.
`
`Programming Example 5.5 An Array-Based Queue
`The first step in designing the queue is to declare the array that we will use for the buffer:
`
`#define Q_SIZE 5 /* your queue size may vary */
`#define Q_MAX (Q_SIZE-1) /* this is the maximum index value into
`the array */
`
`int q[Q_SIZE]; /* the array for our queue */
`int head, tail; /* indexes for the current queue head and tail */
`
`SAMSUNG ELECTRONICS CO., LTD., v. AFFINITY LABS OF TEXAS, LLC
`IPR2014-01181 EXHIBIT 2028 – 11
`
`

`

`222
`
`CHAPTER 5 Program Design and Analysis
`
`The variables head and tail keep track of the two ends of the queue.
`Here is the initialization code for the queue:
`
`void queue_init() {
`
`
`
`
`
`
`
`/* initialize the queue data structure */
`
`head = 0;
`tail = 0;
`}
`
`We initialize the head and tail to the same position. As we add a value to the tail of
`the queue, we will increment tail. Similarly, when we remove a value from the head, we will
`increment head. The value of head is always equal to the location of the first element of the
`queue (except for when the queue is empty). The value of tail, in contrast, points to the
`location in which the next queue entry will go. When we reach the end of the array, we must
`wrap around these values—for example, when we add a value into the last element of q, the
`new value of tail becomes the 0th entry of the array.
`We need to check for two error conditions: removing from an empty queue and adding
`to a full queue. In the first case, we know the queue is empty if head == tail. In the
`second case, we know the queue is full if incrementing tail will cause it to equal head.
`Testing for fullness, however, is a little harder because we have to worry about wraparound.
`Here is the code for adding an element to the tail of the queue, which is known as enqueueing:
`
`void enqueue(int val) {
`/* check for a full queue */
`if (((tail+1) % Q_SIZE) == head) error("enqueue onto full
`
`queue",tail);
`/* add val to the tail of the queue */
`q[tail] = val;
`/* update the tail */
`if (tail == Q_MAX)
`tail = 0;
`else
`tail++;
`
`}
`
`
`
`
`
`
`
`
`
`
`
`
`And here is the code for removing an element from the head of the queue, known as
`dequeueing:
`
`int dequeue() {
` int returnval; /* use this to remember the value that you
`will return */
`
`/* check for an empty queue */
`
`if (head == tail) error("dequeue from empty queue",head);
`
`/* remove from the head of the queue */
`
`returnval = q[head];
`
`/* update head */
`
`if (head == Q_MAX)
`
`
`head = 0;
`
`else
`head++;
`
`
`
`/* return the value */
`
`return returnval;
`
`}
`
`SAMSUNG ELECTRONICS CO., LTD., v. AFFINITY LABS OF TEXAS, LLC
`IPR2014-01181 EXHIBIT 2028 – 12
`
`

`

`Producer/consumer
`
`Data structures in
`queues
`
`5.3 Models of programs
`
`223
`
`q1
`
`p1
`
`q12
`
`p2
`
`q2
`
`FIGURE 5.3
`A producer/consumer system.
`
`Digital filters always take in the same amount of data in each time period. Many
`systems, even signal processing systems, don’t fit that mold. Rather, they may take
`in varying amounts of data over time and produce varying amounts. When several of
`these systems operate in a chain, the variable-rate output of one stage becomes the
`variable-rate input of another stage.
`Figure 5.3 shows a block diagram of a simple producer/consumer system. p1 and
`p2 are the two blocks that perform algorithmic processing. The data is fed to them by
`queues that act as elastic buffers. The queues modify the flow of control in the system
`as well as store data. If, for example, p2 runs ahead of p1, it will eventually run out of
`data in its q12 input queue. At that point, the queue will return an empty signal to p2.
`At this point, p2 should stop working until more data is available. This sort of complex
`control is easier to implement in a multitasking environment, as we will see in Chap-
`ter 6, but it is also possible to make effective use of queues in programs structured as
`nested procedures.
`The queues in a producer/consumer may hold either uniform-sized data elements
`or variable-sized data elements. In some cases, the consumer needs to know how many
`of a given type of data element are associated together. The queue can be structured
`to hold a complex data type. Alternatively, the data structure can be stored as bytes or
`integers in the queue with, for example, the first integer holding the number of succes-
`sive data elements.
`
`5.3 Models of programs
`In this section, we develop models for programs that are more general than source
`code. Why not use the source code directly? First, there are many different types of
`source code—assembly languages, C code, and so on—but we can use a single model
`to describe all of them. Once we have such a model, we can perform many useful
`analyses on the model more easily than we could on the source code.
`Our fundamental model for programs is the control/data flow graph (CDFG).
`(We can also model hardware behavior with the CDFG.) As the name implies,
`the CDFG has constructs that model both data operations (arithmetic and other
`computations) and control operations (conditionals). Part of the power of the
`CDFG comes from its combination of control and data constructs. To understand
`the CDFG, we start with pure data descriptions and then extend the model to
`control.
`
`SAMSUNG ELECTRONICS CO., LTD., v. AFFINITY LABS OF TEXAS, LLC
`IPR2014-01181 EXHIBIT 2028 – 13
`
`

`

`224
`
`CHAPTER 5 Program Design and Analysis
`
`5.3.1 Data flow graphs
`A data flow graph is a model of a program with no conditionals. In a high-level pro-
`gramming language, a code segment with no conditionals—more precisely, with only
`one entry and exit point—is known as a basic block. Figure 5.4 shows a simple basic
`block. As the C code is executed, we would enter this basic block at the beginning and
`execute all the statements.
`Before we are able to draw the data flow graph for this code we need to modify it
`slightly. There are two assignments to the variable x—it appears twice on the left side
`of an assignment. We need to rewrite the code in single-assignment form, in which
`a variable appears only once on the left side. Because our specification is C code, we
`assume that the statements are executed sequentially, so that any use of a variable
`refers to its latest assigned value. In this case, x is not reused in this block (presumably
`it is used elsewhere), so we just have to eliminate the multiple assignment to x. The
`result is shown in Figure 5.5 where we have used the names x1 and x2 to distinguish
`the separate uses of x.
`The single-assignment form is important because it allows us to identify a unique
`location in the code where each named location is computed. As an introduction to the
`data flow graph, we use two types of nodes in the graph—round nodes denote opera-
`tors and square nodes represent values. The value nodes may be either inputs to the
`basic block, such as a and b, or variables assigned to within the block, such as w and
`x1. The data flow graph for our single-assignment code is shown in Figure 5.6. The
`single-assignment form means that the data flow graph is acyclic—if we assigned to x
`multiple times, then the second assignment would form a cycle in the graph including
`x and the operators used to compute x. Keeping the data flow graph acyclic is impor-
`tant in many types of analyses we want to do on the graph. (Of course, it is important
`to know whether the source code actually assigns to a variable multiple times, because
`some of those assignments may be mistakes. We consider the analysis of source code
`for proper use of assignments in Section 5.5.)
`The data flow graph is generally drawn in the form shown in Figure 5.7. Here, the
`variables are not explicitly represented by nodes. Instead, the edges are labeled with
`the variables they represent. As a result, a variable can be represented by more than
`one edge. However, the edges are directed and all the edges for a variable must come
`from a single source. We use this form for its simplicity and compactness.
`
`w 5 a 1 b;
`x 5 a ⫺ c;
`y 5 x 1 d;
`x 5 a 1 c;
`z 5 y 1 e;
`FIGURE 5.4
`A basic block in C.
`
` w ⫽ a ⫹b;
`x1⫽ a ⫺c;
` y ⫽ x1 ⫹d;
`x2 ⫽ a ⫹c;
` z ⫽ y ⫹e;
`
`FIGURE 5.5
`The basic block in single-assignment form.
`
`SAMSUNG ELECTRONICS CO., LTD., v. AFFINITY LABS OF TEXAS, LLC
`IPR2014-01181 EXHIBIT 2028 – 14
`
`

`

`5.3 Models of programs
`
`225
`
`a
`
`b
`
`c
`
`d
`
`e
`
`⫹
`
`x2
`
`⫹
`
`w
`
`⫺
`
`x1
`
`⫹
`
`y
`
`FIGURE 5.6
`An extended data flow graph for our sample basic block.
`
`a
`
`b
`
`c
`
`d
`
`⫹
`
`x2
`
`⫹
`
`w
`
`⫺
`
`x1
`
`⫹
`
`y
`
`FIGURE 5.7
`Standard data flow graph for our sample basic block.
`
`⫹
`
`z
`
`e
`
`⫹
`
`z
`
`SAMSUNG ELECTRONICS CO., LTD., v. AFFINITY LABS OF TEXAS, LLC
`IPR2014-01181 EXHIBIT 2028 – 15
`
`

`

`226
`
`CHAPTER 5 Program Design and Analysis
`
`The data flow graph for the code makes the order in which the operations are per-
`formed in the C code much less obvious. This is one of the advantages of the data flow
`graph. We can use it to determine feasible reorderings of the operations, which may
`help us to reduce pipeline or cache conflicts. We can also use it when the exact order
`of operations simply doesn’t matter. The data flow graph defines a partial ordering of
`the operations in the basic block. We must ensure that a value is computed before it is
`used, but generally there are several possible orderings of evaluating expressions that
`satisfy this requirement.
`
`5.3.2 Control/data flow graphs
`A CDFG uses a data flow graph as an element, adding constructs to describe control.
`In a basic CDFG, we have two types of nodes: decision nodes and data flow nodes.
`A data flow node encapsulates a complete data flow graph to represent a basic block.
`We can use one type of decision node to describe all the types of control in a sequential
`program. (The jump/branch is, after all, the way we implement all those high-level
`control constructs.)
`Figure 5.8 shows a bit of C code with control constructs and the CDFG constructed
`from it. The rectangular nodes in the graph represent the basic blocks. The basic blocks
`in the C code have been represented by function calls for simplicity. The diamond-shaped
`nodes represent the conditionals. The node’s condition is given by the label, and the
`edges are labeled with the possible outcomes of evaluating the condition.
`Building a CDFG for a while loop is straightforward, as shown in Figure 5.9. The
`while loop consists of both a test and a loop body, each of which we know how to rep-
`resent in a CDFG. We can represent for loops by remembering that, in C, a for loop is
`defined in terms of a while loop. This for loop
`
`for (i = 0; i < N; i++) {
`
`loop_body();
`
`} i
`
`s equivalent to
`
`i = 0;
`while (i < N) {
`
`loop_body();
`
`i++;
`
`} F
`
`or a complete CDFG model, we can use a data flow graph t