/[dtapublic]/pubs/books/ucbka/trunk/c_pco0/c_pco0.tex
ViewVC logotype

Diff of /pubs/books/ucbka/trunk/c_pco0/c_pco0.tex

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 139 by dashley, Fri Oct 7 01:36:46 2016 UTC revision 140 by dashley, Mon Jul 3 01:59:16 2017 UTC
# Line 1  Line 1 
1  %$Header: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_pco0/c_pco0.tex,v 1.4 2003/03/03 23:50:43 dtashley Exp $  %$Header$
2    
3  \chapter{\cpcozerolongtitle{}}  \chapter{\cpcozerolongtitle{}}
4    
5  \label{cpco0}  \label{cpco0}
6    
7  \beginchapterquote{``For any serious purpose, intelligence is a very minor gift.''}  \beginchapterquote{``For any serious purpose, intelligence is a very minor gift.''}
8                       {G. H. Hardy, \cite{bibref:b:mathematiciansapology:1940}}                       {G. H. Hardy, \cite{bibref:b:mathematiciansapology:1940}}
9    
10  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
11  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
12  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
13  \section{Introduction}  \section{Introduction}
14  %Section tag: INT0  %Section tag: INT0
15  \label{cpco0:sint0}  \label{cpco0:sint0}
16    
17  In this chapter, we explain in detail the way that  In this chapter, we explain in detail the way that
18  practical microcontroller software is constructed.  practical microcontroller software is constructed.
19  Such discussion is essential for two reasons:  Such discussion is essential for two reasons:
20    
21  \begin{itemize}  \begin{itemize}
22  \item Practical techniques of construction, because they have  \item Practical techniques of construction, because they have
23        been honed over time, usually represent best practices.        been honed over time, usually represent best practices.
24        The techniques presented in this chapter represent worthy        The techniques presented in this chapter represent worthy
25        techniques for constructing embedded systems, and may        techniques for constructing embedded systems, and may
26        serve as a guide for the construction of embedded software.        serve as a guide for the construction of embedded software.
27  \item Software engineers often grasp concepts intuitively that they  \item Software engineers often grasp concepts intuitively that they
28        cannot express formally.  Many of the tendencies and best practices        cannot express formally.  Many of the tendencies and best practices
29        described in this chapter have a formal basis that can and should be        described in this chapter have a formal basis that can and should be
30        studied and investigated.        studied and investigated.
31  \end{itemize}  \end{itemize}
32    
33    
34  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
35  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
36  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
37  \section{Measurement Of Time}  \section{Measurement Of Time}
38  %Section tag: MOT0  %Section tag: MOT0
39  \label{cpco0:smot0}  \label{cpco0:smot0}
40    
41  As we've mentioned previously, most software components in a  As we've mentioned previously, most software components in a
42  typical small embedded system are state machines with transition  typical small embedded system are state machines with transition
43  functions that depend on inputs and on time.  functions that depend on inputs and on time.
44    
45  Because time is such a perasive concept in microcontroller software,  Because time is such a perasive concept in microcontroller software,
46  the decision about how time is to be measured and tested is the  the decision about how time is to be measured and tested is the
47  single most important design decision in terms of ROM consumption.  single most important design decision in terms of ROM consumption.
48    
49    
50  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
51  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
52  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
53  \subsection{Countdown Software Timers}  \subsection{Countdown Software Timers}
54  %Subsection tag: CST0  %Subsection tag: CST0
55  \label{cpco0:smot0:scst0}  \label{cpco0:smot0:scst0}
56    
57  The most common mechanism for allowing state machines to make transitions  The most common mechanism for allowing state machines to make transitions
58  which are partly based on time is the  which are partly based on time is the
59  \index{countdown software timer}\emph{countdown software timer},  \index{countdown software timer}\emph{countdown software timer},
60  which is most commonly called a  which is most commonly called a
61  \index{software timer}\emph{software timer}.  \index{software timer}\emph{software timer}.
62    
63  A software timer is an unsigned byte or word which is decremented at a  A software timer is an unsigned byte or word which is decremented at a
64  periodic rate, but never decremented beyond zero.  All software  periodic rate, but never decremented beyond zero.  All software
65  timers in a system are typically decremented by one system process.  timers in a system are typically decremented by one system process.
66  A process which uses a software timer will set (assign) it to  A process which uses a software timer will set (assign) it to
67  a non-zero value representing a time delay, and then test it against  a non-zero value representing a time delay, and then test it against
68  zero to check if the time delay has elapsed.  This approach has  zero to check if the time delay has elapsed.  This approach has
69  several advantages:  several advantages:
70    
71  \begin{itemize}  \begin{itemize}
72  \item Setting a software timer (assigning it to a non-zero  \item Setting a software timer (assigning it to a non-zero
73        value) is a very inexpensive and compact test.  (Because        value) is a very inexpensive and compact test.  (Because
74        the setting of software timers occurs many times throughout        the setting of software timers occurs many times throughout
75        ROM, this savings can be substantial.  Additionally,        ROM, this savings can be substantial.  Additionally,
76        there is a savings in execution time.)        there is a savings in execution time.)
77  \item A test of a byte against zero is typically a very  \item A test of a byte against zero is typically a very
78        inexpensive and compact test.  (Because tests for        inexpensive and compact test.  (Because tests for
79        expired timers occur many times throughout ROM,        expired timers occur many times throughout ROM,
80        this savings can be substantial.  Additionally, there        this savings can be substantial.  Additionally, there
81        is a large savings in execution time because        is a large savings in execution time because
82        in a typical software load, \emph{many} transition        in a typical software load, \emph{many} transition
83        functions depend on expired timers.)        functions depend on expired timers.)
84  \item Decrements of single bytes, as are required  \item Decrements of single bytes, as are required
85        to decrement software timers, are also inexpensive operations.        to decrement software timers, are also inexpensive operations.
86  \end{itemize}  \end{itemize}
87    
88  Because software timers are either one unsigned byte (8 bits) or  Because software timers are either one unsigned byte (8 bits) or
89  one unsigned word (16 bits), it is not possible to have ``one size  one unsigned word (16 bits), it is not possible to have ``one size
90  fits all'', as the range of a software timer and its precision  fits all'', as the range of a software timer and its precision
91  are mutually exclusive.  Very typically, software timers are arranged  are mutually exclusive.  Very typically, software timers are arranged
92  in either binary decades (for example, 2 ms/count, 4 ms/count,  in either binary decades (for example, 2 ms/count, 4 ms/count,
93  8 ms/count, 16 ms/count, etc.) or in the more conventional  8 ms/count, 16 ms/count, etc.) or in the more conventional
94  1-2-5 decades (for example, 1 ms/count, 2 ms/count, 5 ms/count,  1-2-5 decades (for example, 1 ms/count, 2 ms/count, 5 ms/count,
95  10 ms/count, etc.).  10 ms/count, etc.).
96    
97  Because the process which uses a software timer as a time  Because the process which uses a software timer as a time
98  reference and the process which decrements a software timer  reference and the process which decrements a software timer
99  are asynchronous, a process which sets a software timer has no  are asynchronous, a process which sets a software timer has no
100  control over whether the timer will be decremented for the  control over whether the timer will be decremented for the
101  first time immediately or after the period-per-count of the timer.  first time immediately or after the period-per-count of the timer.
102  Generally, if $\tau$ is the period-per-count of a software timer and  Generally, if $\tau$ is the period-per-count of a software timer and
103  the software timer is set to the value of $N$, the process that  the software timer is set to the value of $N$, the process that
104  sets the software timer can be assured that the time $T$ until the  sets the software timer can be assured that the time $T$ until the
105  software timer reaches zero will meet the inequality  software timer reaches zero will meet the inequality
106    
107  \begin{equation}  \begin{equation}
108  \label{eq:cpco0:smot0:scst0:00}  \label{eq:cpco0:smot0:scst0:00}
109  (N-1) \tau < T \leq N \tau ,  (N-1) \tau < T \leq N \tau ,
110  \end{equation}  \end{equation}
111    
112  \noindent{}where the interval is open on the left because  \noindent{}where the interval is open on the left because
113  it is not possible to test a software timer at  it is not possible to test a software timer at
114  the same instant it is set.  the same instant it is set.
115    
116  Despite the inequality supplied by  Despite the inequality supplied by
117  (\ref{eq:cpco0:smot0:scst0:00}), it is common in practice to calculate  (\ref{eq:cpco0:smot0:scst0:00}), it is common in practice to calculate
118  the value to which a software timer should be set as  the value to which a software timer should be set as
119    
120  \begin{equation}  \begin{equation}
121  \label{eq:cpco0:smot0:scst0:01}  \label{eq:cpco0:smot0:scst0:01}
122  N = \left\lfloor { \frac{T}{\tau} } \right\rfloor .  N = \left\lfloor { \frac{T}{\tau} } \right\rfloor .
123  \end{equation}  \end{equation}
124    
125  (\ref{eq:cpco0:smot0:scst0:01}) is commonly used because there  (\ref{eq:cpco0:smot0:scst0:01}) is commonly used because there
126  are other sources of delay in a software system that compensate  are other sources of delay in a software system that compensate
127  for the lower bound in (\ref{eq:cpco0:smot0:scst0:00}), and because  for the lower bound in (\ref{eq:cpco0:smot0:scst0:00}), and because
128  values of $N$ are seldom close to zero, so any error due to the  values of $N$ are seldom close to zero, so any error due to the
129  lower bound is small in relation to $T$.  lower bound is small in relation to $T$.
130    
131  It is also instructive to calculate the maximum ``coarseness'' when  It is also instructive to calculate the maximum ``coarseness'' when
132  software timers are arranged in binary decades or 1-2-5 decades  software timers are arranged in binary decades or 1-2-5 decades
133  and consequently a period-per-count $\tau$ which precisely accomodates  and consequently a period-per-count $\tau$ which precisely accomodates
134  the maximum period $T$ cannot be chosen.  In the case of binary decades,  the maximum period $T$ cannot be chosen.  In the case of binary decades,
135  the inequality  the inequality
136    
137  \begin{equation}  \begin{equation}
138  \label{eq:cpco0:smot0:scst0:02}  \label{eq:cpco0:smot0:scst0:02}
139  \frac{255}{2} \tau < T \leq 255 \tau  \frac{255}{2} \tau < T \leq 255 \tau
140  \end{equation}  \end{equation}
141    
142  \noindent{}holds, as if it were true that $T \leq 255 \tau /2$,  \noindent{}holds, as if it were true that $T \leq 255 \tau /2$,
143  then we would choose  then we would choose
144  a software timer with the next smaller period $\tau ' = \tau / 2$.  a software timer with the next smaller period $\tau ' = \tau / 2$.
145  Thus we are always assured that  Thus we are always assured that
146    
147  \begin{equation}  \begin{equation}
148  \label{eq:cpco0:smot0:scst0:03}  \label{eq:cpco0:smot0:scst0:03}
149  \tau < 127.5 T .  \tau < 127.5 T .
150  \end{equation}  \end{equation}
151    
152  \noindent{}Thus, with a binary decade arrangement of software timers, we  \noindent{}Thus, with a binary decade arrangement of software timers, we
153  can always choose the timer period $N \tau$ with a granularity of about  can always choose the timer period $N \tau$ with a granularity of about
154  1 part in 127.5 or better.  1 part in 127.5 or better.
155    
156  The analogous question for software timers arranged in 1-2-5 decades  The analogous question for software timers arranged in 1-2-5 decades
157  leads to this inequality:  leads to this inequality:
158    
159  \begin{equation}  \begin{equation}
160  \label{eq:cpco0:smot0:scst0:04}  \label{eq:cpco0:smot0:scst0:04}
161  \frac{255}{2.5} \tau < T \leq 255 \tau ,  \frac{255}{2.5} \tau < T \leq 255 \tau ,
162  \end{equation}  \end{equation}
163    
164  \noindent{}where the factor ``2.5'' appears because the largest  \noindent{}where the factor ``2.5'' appears because the largest
165  change in $\tau$ will occur from ``2'' to ``5'' in a 1-2-5 decade  change in $\tau$ will occur from ``2'' to ``5'' in a 1-2-5 decade
166  arrangement.  Again, the same argument made earlier  arrangement.  Again, the same argument made earlier
167  applies---if $T \leq 255 \tau / 2.5$, then it would \emph{always}  applies---if $T \leq 255 \tau / 2.5$, then it would \emph{always}
168  be possible to choose a software timer with the next smaller period.  be possible to choose a software timer with the next smaller period.
169  Thus we are always assured that  Thus we are always assured that
170    
171  \begin{equation}  \begin{equation}
172  \label{eq:cpco0:smot0:scst0:05}  \label{eq:cpco0:smot0:scst0:05}
173  \tau < 102 T .  \tau < 102 T .
174  \end{equation}  \end{equation}
175    
176  \noindent{}Thus, with a 1-2-5 decade arrangement of software timers, we  \noindent{}Thus, with a 1-2-5 decade arrangement of software timers, we
177  can always choose the timer period $N \tau$ with a granularity of about  can always choose the timer period $N \tau$ with a granularity of about
178  1 part in 102 or better.  1 part in 102 or better.
179    
180    
181  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
182  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
183  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
184  \subsection{On-Demand Two's Complement Timekeeping}  \subsection{On-Demand Two's Complement Timekeeping}
185  %Subsection tag: ODT0  %Subsection tag: ODT0
186  \label{cpco0:smot0:sodt0}  \label{cpco0:smot0:sodt0}
187    
188  Often, software timers as described in Section \ref{cpco0:smot0:scst0}  Often, software timers as described in Section \ref{cpco0:smot0:scst0}
189  immediately above won't meet a particular timing requirement because  immediately above won't meet a particular timing requirement because
190  the period to be measured is quite large, but it must be measured with  the period to be measured is quite large, but it must be measured with
191  fair precision.\footnote{A typical requirement with these characteristics  fair precision.\footnote{A typical requirement with these characteristics
192  is that a delay be 60 minutes $\pm$ 5 seconds.  This requirement  is that a delay be 60 minutes $\pm$ 5 seconds.  This requirement
193  represents a precision of 1 part in 720, which is more precision  represents a precision of 1 part in 720, which is more precision
194  than a 1-byte software timer can offer.}    than a 1-byte software timer can offer.}  
195    
196  In such situations, one  In such situations, one
197  option is to offer extended-precision (i.e. 16- or 24-bit) software timers.  option is to offer extended-precision (i.e. 16- or 24-bit) software timers.
198  However, another popular option is to provide a function call which  However, another popular option is to provide a function call which
199  will allow retrieval of the most precise time measurement available,  will allow retrieval of the most precise time measurement available,
200  typically maintained as a multiple-precision integer.  A typical  typically maintained as a multiple-precision integer.  A typical
201  design decision in microcontroller work would be a 5-byte multiple-precision  design decision in microcontroller work would be a 5-byte multiple-precision
202  integer counter, maintaining the number of milliseconds since the  integer counter, maintaining the number of milliseconds since the
203  microcontroller was reset.  Such a counter will measure time periods  microcontroller was reset.  Such a counter will measure time periods
204  of up to about 35 years.  of up to about 35 years.
205    
206  Note that in using the value obtained from a function call  Note that in using the value obtained from a function call
207  which obtains a maximum-precision time count, it is not  which obtains a maximum-precision time count, it is not
208  necessary to use all the bytes of the result.  For example,  necessary to use all the bytes of the result.  For example,
209  using the least significant two bytes of such a counter  using the least significant two bytes of such a counter
210  (assuming that the counter represents milliseconds) will  (assuming that the counter represents milliseconds) will
211  allow the measurement of time periods up to about 65 seconds  allow the measurement of time periods up to about 65 seconds
212  with 1ms of resolution.  with 1ms of resolution.
213    
214    
215  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
216  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
217  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
218  \subsection{Invocation Counting}  \subsection{Invocation Counting}
219  %Subsection tag: ICN0  %Subsection tag: ICN0
220  \label{cpco0:smot0:sicn0}  \label{cpco0:smot0:sicn0}
221    
222    
223    
224  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
225  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
226  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
227  \subsection{Timer Events}  \subsection{Timer Events}
228  %Subsection tag: TEV0  %Subsection tag: TEV0
229  \label{cpco0:smot0:stev0}  \label{cpco0:smot0:stev0}
230    
231    
232    
233  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
234  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
235  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
236  \section{Interface Styles}  \section{Interface Styles}
237  %Section tag: IST0  %Section tag: IST0
238  \label{cpco0:sist0}  \label{cpco0:sist0}
239    
240  Without exception, the paradigm of decomposition for small microcontroller  Without exception, the paradigm of decomposition for small microcontroller
241  software is a collection of concurrent cooperating state machines.  In other  software is a collection of concurrent cooperating state machines.  In other
242  words, we imagine  words, we imagine
243  the software system as collection of state machines\footnote{\ldots{} or processes or  the software system as collection of state machines\footnote{\ldots{} or processes or
244  timed automatons or elementary hybrid machines or state machine thingies  timed automatons or elementary hybrid machines or state machine thingies
245  or thingamabobs or whatever it is in your lingo, man \ldots{}.} which are  or thingamabobs or whatever it is in your lingo, man \ldots{}.} which are
246  \emph{independent} or \emph{concurrent}:  that is, they can in most  \emph{independent} or \emph{concurrent}:  that is, they can in most
247  cases change state independently  cases change state independently
248  of one another.  However, at the same time, we envision these  of one another.  However, at the same time, we envision these
249  state machines as \emph{cooperating}:  that is, they have ways  state machines as \emph{cooperating}:  that is, they have ways
250  of exchanging information and of synchronizing when necessary.  of exchanging information and of synchronizing when necessary.
251    
252  In this section, we enumerate and discuss all of the interface  In this section, we enumerate and discuss all of the interface
253  types between  types between
254  concurrent cooperating state machines.  concurrent cooperating state machines.
255    
256    
257  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
258  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
259  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
260  \subsection[1-Writer $n$-Reader RAM Variable Interface]  \subsection[1-Writer $n$-Reader RAM Variable Interface]
261             {1-Writer \mbox{\boldmath $n$}-Reader RAM Variable Interface}             {1-Writer \mbox{\boldmath $n$}-Reader RAM Variable Interface}
262  %Subsection tag: own0  %Subsection tag: own0
263  \label{cpco0:sist0:sown0}  \label{cpco0:sist0:sown0}
264    
265    
266  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
267  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
268  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
269  \subsection{Finite State Machine RAM Variable Interface}  \subsection{Finite State Machine RAM Variable Interface}
270  %Subsection tag: fsm0  %Subsection tag: fsm0
271  \label{cpco0:sist0:sfsm0}  \label{cpco0:sist0:sfsm0}
272    
273    
274  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
275  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
276  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
277  \subsubsection{The General FSM RAM Variable Interface}  \subsubsection{The General FSM RAM Variable Interface}
278  %Subsubsection tag: gfs0  %Subsubsection tag: gfs0
279  \label{cpco0:sist0:sfsm0:sgfs0}  \label{cpco0:sist0:sfsm0:sgfs0}
280    
281    
282  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
283  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
284  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
285  \subsubsection{The RAM Variable Semaphore}  \subsubsection{The RAM Variable Semaphore}
286  %Subsubsection tag: rvs0  %Subsubsection tag: rvs0
287  \label{cpco0:sist0:sfsm0:srvs0}  \label{cpco0:sist0:sfsm0:srvs0}
288    
289    
290  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
291  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
292  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
293  \section{Reduction Of Combinational Mappings}  \section{Reduction Of Combinational Mappings}
294    
295    
296    
297  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
298  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
299  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
300  \section{Reduction Of Sequential Mappings}  \section{Reduction Of Sequential Mappings}
301    
302    
303    
304  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
305  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
306  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
307  \section{Debouncing}  \section{Debouncing}
308    
309    
310    
311  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
312  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
313  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
314  \section{Filtering}  \section{Filtering}
315    
316    
317    
318  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
319  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
320  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
321  \section{ROM Reduction Techniques}  \section{ROM Reduction Techniques}
322  %Section tag: rrs0  %Section tag: rrs0
323  \label{cpco0:srrs0}  \label{cpco0:srrs0}
324    
325  Microcontroller products are very sensitive to ROM consumption, and  Microcontroller products are very sensitive to ROM consumption, and
326  a primary goal is to create a software load that meets all requirements  a primary goal is to create a software load that meets all requirements
327  with minimal ROM.  Semiconductor manufacturers often design  with minimal ROM.  Semiconductor manufacturers often design
328  microcontroller families so that there is a continuum of microcontroller  microcontroller families so that there is a continuum of microcontroller
329  variants which differ only in the amount of ROM and RAM available,  variants which differ only in the amount of ROM and RAM available,
330  and in some cases a microcontroller software developer is able to  and in some cases a microcontroller software developer is able to
331  substitute a different part with more ROM if a ROM boundary is reached.  substitute a different part with more ROM if a ROM boundary is reached.
332  However, semiconductor manufacturers always create a pricing schema  However, semiconductor manufacturers always create a pricing schema
333  where the part with more ROM costs more, and so even if a part with  where the part with more ROM costs more, and so even if a part with
334  more ROM is available, there may be substantial management pressure to  more ROM is available, there may be substantial management pressure to
335  shoehorn a software load into the smaller part rather than use the  shoehorn a software load into the smaller part rather than use the
336  more expensive part. In many cases, no substitute part with more ROM  more expensive part. In many cases, no substitute part with more ROM
337  is available, so the software load \emph{must} fit.  is available, so the software load \emph{must} fit.
338    
339  In this section, we discuss strategies for reducing ROM consumption  In this section, we discuss strategies for reducing ROM consumption
340  in an embedded software load.  For the most part, these are strategies  in an embedded software load.  For the most part, these are strategies
341  that can be adopted retroactively when a software load does not fit.  that can be adopted retroactively when a software load does not fit.
342  However, it should also be noted that ROM efficiency \emph{starts}  However, it should also be noted that ROM efficiency \emph{starts}
343  with using some of the construction techniques presented in this chapter  with using some of the construction techniques presented in this chapter
344  in order to create a ROM-efficient system from the start.  For example,  in order to create a ROM-efficient system from the start.  For example,
345  an inefficient design decision regarding the measurement of time  an inefficient design decision regarding the measurement of time
346  would be hard to recover from.  would be hard to recover from.
347    
348    
349  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
350  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
351  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
352  \subsection{Modifying The Largest Software Component First}  \subsection{Modifying The Largest Software Component First}
353  %Subsection tag: mlf0  %Subsection tag: mlf0
354  \label{cpco0:srrs0:smlf0}  \label{cpco0:srrs0:smlf0}
355    
356  One observation which is helpful is that the largest software components  One observation which is helpful is that the largest software components
357  in a system tend to have the most absolute ROM waste.\footnote{Thanks  in a system tend to have the most absolute ROM waste.\footnote{Thanks
358  to Lou Miller \cite{bibref:i:loumiller} for this insight.}    to Lou Miller \cite{bibref:i:loumiller} for this insight.}  
359  Therefore, the quickest way to significantly reduce the ROM consumption  Therefore, the quickest way to significantly reduce the ROM consumption
360  of an embedded software load is often to analyze and optimize the  of an embedded software load is often to analyze and optimize the
361  largest software component.  largest software component.
362    
363    
364  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
365  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
366  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
367  \subsection{Optimizing \emph{near} Versus \emph{far} Allocation Of RAM}  \subsection{Optimizing \emph{near} Versus \emph{far} Allocation Of RAM}
368  %Subsection tag: nvf0  %Subsection tag: nvf0
369  \label{cpco0:srrs0:snvf0}  \label{cpco0:srrs0:snvf0}
370    
371  Many microcontrollers have two different categories of RAM, which are  Many microcontrollers have two different categories of RAM, which are
372  usually called \emph{near} and \emph{far} RAM; although some microcontrollers  usually called \emph{near} and \emph{far} RAM; although some microcontrollers
373  use different nomenclature---for example \emph{zero page} RAM rather than  use different nomenclature---for example \emph{zero page} RAM rather than
374  \emph{near} RAM.  Usually, \emph{near} and \emph{far} are also  \emph{near} RAM.  Usually, \emph{near} and \emph{far} are also
375  the `C' keywords used.  the `C' keywords used.
376    
377  Usually, \emph{near} RAM has three advantages over \emph{far} RAM:  Usually, \emph{near} RAM has three advantages over \emph{far} RAM:
378    
379  \begin{itemize}  \begin{itemize}
380  \item Machine instructions to access (load, store, test, perform  \item Machine instructions to access (load, store, test, perform
381        arithmetic on) near RAM locations are more compact than the        arithmetic on) near RAM locations are more compact than the
382        corresponding instructions on far RAM.  This normally comes        corresponding instructions on far RAM.  This normally comes
383        directly from the machine-language encoding of instructions:        directly from the machine-language encoding of instructions:
384        most typically the address of a near location requires one byte        most typically the address of a near location requires one byte
385        to encode while the address of a far location requires two.        to encode while the address of a far location requires two.
386  \item Machine instructions to access (load, store, test, perform  \item Machine instructions to access (load, store, test, perform
387        arithmetic on) near RAM locations require less time to        arithmetic on) near RAM locations require less time to
388        execute than the        execute than the
389        corresponding instructions on far RAM.  This is normally        corresponding instructions on far RAM.  This is normally
390        strongly related to the more compact encoding, as there        strongly related to the more compact encoding, as there
391        are fewer ROM fetches involved.        are fewer ROM fetches involved.
392  \item In many cases, certain instructions can operate only on near  \item In many cases, certain instructions can operate only on near
393        operands.  This means that certain operations applied to        operands.  This means that certain operations applied to
394        near operands require only one machine instruction,        near operands require only one machine instruction,
395        but require at least three (load, operate, store) when        but require at least three (load, operate, store) when
396        applied to far operands.        applied to far operands.
397  \end{itemize}  \end{itemize}
398    
399  It is intuitively clear that to minimize ROM consumption, assuming that  It is intuitively clear that to minimize ROM consumption, assuming that
400  we have a limited amount of near RAM and cannot place all variables  we have a limited amount of near RAM and cannot place all variables
401  in near RAM, we must place the most frequently-accessed (throughout  in near RAM, we must place the most frequently-accessed (throughout
402  all of ROM) variables in near RAM.  all of ROM) variables in near RAM.
403    
404  In practice, the allocation of most frequently accessed variables to  In practice, the allocation of most frequently accessed variables to
405  near RAM happens both formally and informally in microcontroller  near RAM happens both formally and informally in microcontroller
406  software developments.    software developments.  
407    
408  Informally, it occurs because it is known  Informally, it occurs because it is known
409  from experience that certain RAM variables are frequently accessed  from experience that certain RAM variables are frequently accessed
410  and should be placed in near RAM---for example, in most automobile  and should be placed in near RAM---for example, in most automobile
411  modules, ignition switch position is referenced many times throughout  modules, ignition switch position is referenced many times throughout
412  ROM and software developers know from experience that this is best placed  ROM and software developers know from experience that this is best placed
413  in near RAM.  in near RAM.
414    
415  Formally, software developers often produce home-made tools to analyze  Formally, software developers often produce home-made tools to analyze
416  the number of times throughout ROM that each variable is referenced, and then  the number of times throughout ROM that each variable is referenced, and then
417  use this information to allocate variables into near and far RAM.  use this information to allocate variables into near and far RAM.
418  Unfortunately, this process is usually manual and cumbersome.  Unfortunately, this process is usually manual and cumbersome.
419  To the best of our knowledge, as of 9/2001, no compiler will analyze  To the best of our knowledge, as of 9/2001, no compiler will analyze
420  variable reference information and allocate variables automatically.  variable reference information and allocate variables automatically.
421  (The best way to accompish this would probably to introduce an  (The best way to accompish this would probably to introduce an
422  addtional keyword that advises the development tools to analyze  addtional keyword that advises the development tools to analyze
423  the number of references and automatically choose whether a variable should be  the number of references and automatically choose whether a variable should be
424  near or far.  \texttt{autonearfar} strikes us as a suitably  near or far.  \texttt{autonearfar} strikes us as a suitably
425  suggestive keyword.)  suggestive keyword.)
426    
427    
428  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
429  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
430  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
431  \subsection{Storage Of Intermediate Results In Near RAM}  \subsection{Storage Of Intermediate Results In Near RAM}
432  %Subsection tag: sir0  %Subsection tag: sir0
433  \label{cpco0:srrs0:ssir0}  \label{cpco0:srrs0:ssir0}
434    
435    
436  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
437  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
438  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
439  \subsection{Suppression Of \emph{Else} Clauses}  \subsection{Suppression Of \emph{Else} Clauses}
440  %Subsection tag: sec0  %Subsection tag: sec0
441  \label{cpco0:srrs0:ssec0}  \label{cpco0:srrs0:ssec0}
442    
443    
444  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
445  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
446  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
447  \subsection{Reassignment Of State Variable State Values}  \subsection{Reassignment Of State Variable State Values}
448  %Subsection tag: rsv0  %Subsection tag: rsv0
449  \label{cpco0:srrs0:srsv0}  \label{cpco0:srrs0:srsv0}
450    
451  Generally, a state machine constains both a discrete state and a  Generally, a state machine constains both a discrete state and a
452  ``continuous'' state (software timers).  (In the strictest sense,  ``continuous'' state (software timers).  (In the strictest sense,
453  the software timers are not discrete state, but they are typically  the software timers are not discrete state, but they are typically
454  modeled this way.)  It can be advantageous to give careful thought  modeled this way.)  It can be advantageous to give careful thought
455  to how the numerical values of discrete states are assigned.  to how the numerical values of discrete states are assigned.
456    
457  The following observations can be made about the influence of the  The following observations can be made about the influence of the
458  numerical values of discrete states on ROM consumption:  numerical values of discrete states on ROM consumption:
459    
460  \begin{itemize}  \begin{itemize}
461  \item Tests against zero may sometimes be cheaper than  \item Tests against zero may sometimes be cheaper than
462        tests against any other value (depending on the processor        tests against any other value (depending on the processor
463        instruction set).  This may imply that the numerical value        instruction set).  This may imply that the numerical value
464        of zero should be assigned to the state which is most        of zero should be assigned to the state which is most
465        often tested for.        often tested for.
466  \item In some cases, assignment to zero may be cheaper than  \item In some cases, assignment to zero may be cheaper than
467        assignment to any other value (i.e. a ``clear" instruction        assignment to any other value (i.e. a ``clear" instruction
468        versus a ``set'' instruction, depending on the instruction        versus a ``set'' instruction, depending on the instruction
469        set).  This may imply that        set).  This may imply that
470        the numerical value of zero should be assigned to the        the numerical value of zero should be assigned to the
471        state with the most incoming transitions.        state with the most incoming transitions.
472  \item It may frequently occur that tests for which discrete  \item It may frequently occur that tests for which discrete
473        state the system is in are seeking to detect        state the system is in are seeking to detect
474        not a single state, but rather a group of states (i.e.        not a single state, but rather a group of states (i.e.
475        \texttt{if ((state == STATE\_1) || (state == STATE\_2) || \ldots{} )}).        \texttt{if ((state == STATE\_1) || (state == STATE\_2) || \ldots{} )}).
476        In such cases, it may be advantageous to assign numerical values        In such cases, it may be advantageous to assign numerical values
477        to make such tests more economical, i.e. it may be advantageous        to make such tests more economical, i.e. it may be advantageous
478        to ``equivalence class'' states (we discuss this in subsequent        to ``equivalence class'' states (we discuss this in subsequent
479        paragraphs).        paragraphs).
480  \end{itemize}  \end{itemize}
481    
482  We should add more about the equivalence classing of states.  In this  We should add more about the equivalence classing of states.  In this
483  context, we mean equivalence classing under the instruction set of the  context, we mean equivalence classing under the instruction set of the
484  microcontroller.  That is, we seek to find some way to assign numerical  microcontroller.  That is, we seek to find some way to assign numerical
485  values to states so that some instruction (\emph{any} instruction!) will  values to states so that some instruction (\emph{any} instruction!) will
486  break them into the classes we desire.  It is also noteworthy that we seek  break them into the classes we desire.  It is also noteworthy that we seek
487  as much flexibility (as many options) as possible, because we may wish to  as much flexibility (as many options) as possible, because we may wish to
488  create more than two equivalence classes, and we may also  create more than two equivalence classes, and we may also
489  wish for some states to appear in more than one equivalence class.  wish for some states to appear in more than one equivalence class.
490    
491  Examples of methods to equivalence class are:  Examples of methods to equivalence class are:
492    
493  \begin{itemize}  \begin{itemize}
494  \item Using a bitwise ``AND'' instruction to mask out all  \item Using a bitwise ``AND'' instruction to mask out all
495        but $n$ bits (of an $N$-bit state variable)        but $n$ bits (of an $N$-bit state variable)
496        and test the result        and test the result
497        against zero.  This creates two equivalence        against zero.  This creates two equivalence
498        classes, one of cardinality $2^{N-n}$        classes, one of cardinality $2^{N-n}$
499        and the other of cardinality        and the other of cardinality
500        $2^N - 2^{N-n} = (2^n - 1)(2^{N-n})$.        $2^N - 2^{N-n} = (2^n - 1)(2^{N-n})$.
501  \item Testing (comparing) against a specific value.  This creates  \item Testing (comparing) against a specific value.  This creates
502        equivalence classes of arbitrary cardinality.        equivalence classes of arbitrary cardinality.
503  \end{itemize}  \end{itemize}
504    
505    
506    
507    
508  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
509  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
510  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
511  \subsection{Factoring Of \emph{Any} Repeated Operation}  \subsection{Factoring Of \emph{Any} Repeated Operation}
512  %Subsection tag: far0  %Subsection tag: far0
513  \label{cpco0:srrs0:sfar0}  \label{cpco0:srrs0:sfar0}
514    
515  In a typical microcontroller, a subroutine call requires three bytes in ROM  In a typical microcontroller, a subroutine call requires three bytes in ROM
516  (one byte for the opcode, and two for the address).  Thus, for any  (one byte for the opcode, and two for the address).  Thus, for any
517  repeated operation which requires over three bytes to accomplish,  repeated operation which requires over three bytes to accomplish,
518  it normally is most effective to place the operation in a subroutine.  it normally is most effective to place the operation in a subroutine.
519  Such a technique will exact a performance penalty in exchange for  Such a technique will exact a performance penalty in exchange for
520  ROM savings.  ROM savings.
521    
522  Most commonly, such a technique is applied to variable assignments which  Most commonly, such a technique is applied to variable assignments which
523  accompany state transitions.  However, it can also be applied  accompany state transitions.  However, it can also be applied
524  to subexpressions in state transition functions.  to subexpressions in state transition functions.
525    
526    
527  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
528  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
529  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
530  \subsection{Factoring Of State Transition Functions And Transitions}  \subsection{Factoring Of State Transition Functions And Transitions}
531  %Subsection tag: fst0  %Subsection tag: fst0
532  \label{cpco0:srrs0:sfst0}  \label{cpco0:srrs0:sfst0}
533    
534    
535    
536  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
537  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
538  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
539  \section{Initialization}  \section{Initialization}
540    
541    
542    
543  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
544  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
545  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
546  \section{The Interrupt Subsystem}  \section{The Interrupt Subsystem}
547    
548    
549    
550  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
551  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
552  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
553  \section{Sleep And Wakeup}  \section{Sleep And Wakeup}
554    
555    
556    
557  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
558  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
559  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
560  \vfill  \vfill
561  \noindent\begin{figure}[!b]  \noindent\begin{figure}[!b]
562  \noindent\rule[-0.25in]{\textwidth}{1pt}  \noindent\rule[-0.25in]{\textwidth}{1pt}
563  \begin{tiny}  \begin{tiny}
564  \begin{verbatim}  \begin{verbatim}
565  $RCSfile: c_pco0.tex,v $  $RCSfile: c_pco0.tex,v $
566  $Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_pco0/c_pco0.tex,v $  $Source: /home/dashley/cvsrep/e3ft_gpl01/e3ft_gpl01/dtaipubs/esrgubka/c_pco0/c_pco0.tex,v $
567  $Revision: 1.4 $  $Revision: 1.4 $
568  $Author: dtashley $  $Author: dtashley $
569  $Date: 2003/03/03 23:50:43 $  $Date: 2003/03/03 23:50:43 $
570  \end{verbatim}  \end{verbatim}
571  \end{tiny}  \end{tiny}
572  \noindent\rule[0.25in]{\textwidth}{1pt}  \noindent\rule[0.25in]{\textwidth}{1pt}
573  \end{figure}  \end{figure}
574    
575  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%  %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
576  % $Log: c_pco0.tex,v $  % $Log: c_pco0.tex,v $
577  % Revision 1.4  2003/03/03 23:50:43  dtashley  % Revision 1.4  2003/03/03 23:50:43  dtashley
578  % Substantial edits.  Safety checkin.  % Substantial edits.  Safety checkin.
579  %  %
580  % Revision 1.3  2001/09/12 18:08:34  dtashley  % Revision 1.3  2001/09/12 18:08:34  dtashley
581  % Closing book project temporarily as returning to school for Ph.D.  % Closing book project temporarily as returning to school for Ph.D.
582  %  %
583  % Revision 1.2  2001/08/31 23:11:17  dtashley  % Revision 1.2  2001/08/31 23:11:17  dtashley
584  % End of August 2001 safety check-in.  % End of August 2001 safety check-in.
585  %  %
586  % Revision 1.1  2001/08/25 22:51:26  dtashley  % Revision 1.1  2001/08/25 22:51:26  dtashley
587  % Complex re-organization of book.  % Complex re-organization of book.
588  %  %
589  %End of file C_PCO0.TEX  %End of file C_PCO0.TEX

Legend:
Removed from v.139  
changed lines
  Added in v.140

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25