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

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

Parent Directory Parent Directory | Revision Log Revision Log


Revision 6 - (show annotations) (download) (as text)
Fri Oct 7 01:36:46 2016 UTC (6 years, 7 months ago) by dashley
File MIME type: application/x-tex
File size: 26088 byte(s)
Initial commit after migrating from CVS.
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

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25