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