Philippe Darche "Microprocessor 4"

1.2.4.5.1. Circular addressing

Digital signal processing consists of digitizing samples x

(i ∈ [0, ∞]) of the signal that are stored in memory, then carrying out a mathematical processing such as filtering on them to then reconstruct the analog signal. To simplify the discourse, memorization of coefficients needed for the calculation is not attempted. The sample flow is of infinite length, and the calculation is only made on a limited number of consecutive samples on the sampled sequence. This set is called a “window”. Linear addressing of the buffer FIFO (First In, First Out) illustrated in Figure 1.23a is not well adapted as it is necessary to test whether the pointers have reached the end. Moreover, the size of the buffer is necessarily high. The circular buffer (ring or cyclic buffer, circular queue), that Figure 1.23b shows, is a much better solution as it makes it possible to decrease its size to that of the window of samples needed for the calculation.

Figure 1.23.Window of five samples

Circular or modulo addressing makes it possible to implement a circular buffer in a Random Access Memory (RAM). As shown in Figure 1.24, it is necessary to have four pieces of information that are the size of the circular buffer L, the address of the base of buffer B, the index pointer of the buffer I and increment (relative integer) M. This addressing uses modular arithmetic where the extent of the values is finite to calculate the pointer addresses. The benefit of using it lies in the fact that a block of L contiguous memory words is addressed by a pointer that uses a modulo addressing L. This means that once a pointer arrives at the end of a buffer, it is reinitialized to point the other end (more precisely, modulo addressing is the capacity to memorize the buffer).

Figure 1.24.Circular buffer

This is conveyed in algorithmic form by:

0 < |M| ≤ L

I в†ђ I + M

if M > 0

then

1 if I ≥ B + L

2В then I в†ђ I - L; buffer overflow or overflow from above

3В end_if

otherwise

1В if I < B

2В then I в†ђ I + L; buffer overflow or overflow from below

3В end_if

4В end_if

Management logic detects a buffer overflow when there is a wraparound. It then generates an interrupt request (see Chapter 5 (#u5f78735e-811e-5ad6-a5c2-c018f246a2e3)) to warn the handler. This automatic management avoids a costly rearrangement of data by shifting them (Figure 1.25(a)) and a permanent monitoring of the pointer value to know whether it has reached an end of the buffer in order to reinitialize it. It frees useful calculating power for processing. For example, as soon as the top of the buffer is reached, the following sample is stored at its start (Figure 1.25(b)).

Figure 1.25.Comparison between linear and circular addressings (from Rao (2001))

The use domain is digital signal filtering carried out by a DSP where digital values, the results of a quantification of an analog signal, are stored in a delay line that can be implemented with a circular buffer in place of carrying out costly temporal shifts. The DSP ADSP-210xx family from Analog Devices uses this mode. One example of use is implementation of a Finite Impulse Response (FIR) described in В§ V3-5.2.

1.2.4.5.2. Reverse bit order addressing

Bit-reversed addressing makes it possible to manipulate materially the address without changing the source address. When the processor is set in this specific mode by the positioning of a flag (cf. В§ V3-3.1.5) in a control register, the address generator (AGU for Address Generation Unit, also called DAG for Data Address Generator or ACU for Address Computation Unit) generates bit-reversed addressing. This means that the LSbs (Least Significant bits) and MSb are exchanged, position 1 and m-2 bits are exchanged and so on (change from little- endian order to big-endian order or vice versa). This mode is used in implementation of the Fast Fourier Transform (FFT) algorithm (Cooley and Tukey 1965), an effective method for calculating a Discrete Fourier Transform (DFT), used for filtering or spectral analysis. Remember that the FFT makes it possible to change the time domain to the frequency domain and vice versa. The problem is that the result output order differs from that of the input or vice versa. This mode makes it possible to preserve the initial order of the data by choosing out-of-order input samples to keep the output order of the data results identical to that of the input. Figure 1.26 shows the details of the calculation of a DIT (Decimal-In-Time) FFT, which is characterized by the inversion placed at the start, compared to calculation of a DIF (Decimal-In-Frequency) FFT, where the inverter is at the end. Each node represents a complex addition (in an imaginary sense). Without going into detail, note the value of the sample indices before and after inverting the order of their binary digits.

is the twiddle factor, also called a Fourier coefficient or an nth root of unity. The dsPIC

microcontroller family from Microchip, DSP32xx from AT&T and DSPs from the SHARC

(DSP-21xxx) family from Analog Devices with the instruction bitrev that reverse the content of a register are examples of components offering it. The mac instruction was introduced into DSPs for this type of calculation (cf. В§ 2.8.4.2).

Figure 1.26.Flow diagram of the algorithm of an 8-point FFT DIT in base 2

To carry out this inversion of the address bit order, Reverse-Carry Arithmetic (RCA) is used. The sub-set managing the address or AGU (cf. В§ V3-3.4.4) reverses the direction of the bits retained when an increment is added to the value of an address register. Two processors that implement it are DSP32xx from AT&T and DSP56000 (Motorola 1992). The AGU also implements linear and modulo arithmetic.

1.2.4.5.3. Linear addressing

The DSP56000 uses a – perhaps poorly named – address modifier. It makes it possible to jump address at each access with a stored constant memorization in a register. The benefit is easy access to the elements of a complex data structure.

1.2.4.6. Modes specific to the assembler

The assembler can offer addressing modes that do not exist in the MPU. Each instruction using them will be replaced by an equivalent logical sequence. One example is symbolic addressing, which facilitates programming of a jump to a specific location in the code marked by a symbolic name called a label (cf. В§ V5-1.3.3). This mode belongs to assembly language (cf. В§ V5-1.3), unlike those seen previously in this chapter which belong to machine language. It is used to make a jump to a precise place in the code marked by this symbolic name. One example is MPU MIPS R2000/R3000 (Kane 1988).

1.2.4.7. Obsolete modes

The modes studied so far are those that are currently available. Some modes have been abandoned because they are complex or not useful. For example, pagezero and direct paged modes (microprocessor IM6100 from Intersil) with current memory sizes are no longer required. We also mention truncation, which consists of deleting the most significant address bits to adapt to addressing capacity in the storage hierarchy considered (Brooks 1962).

1.2.4.8. Note

Sequential execution of instructions in von Neumann architecture (cf. В§ V1-3.2.2) can be seen as a sequential addressing mode (source: Wikipedia).

1.2.5. Summary on addressing

Addressing modes have evolved to meet needs in the software industry to improve efficiency of programs and facilitate implementing functionalities of high- level languages as their control structures. It is useful to class addressing modes depending on their content, code or data. Simple code addressing modes are Program Counter (PC)-relative absolute addressings and indirect register addressings. Sequential execution by nop instruction can be seen as an addressing mode. Sample data addressing modes are immediate, (direct) register, implicit and base plus offset modes. Mixed (code/data) modes are direct absolute and indexed, base plus index modes with or without offset (base plus index plus offset), scaled indexed modes, register indirect modes, indirect register modes with auto-increment, indirect memory and PC-relative modes.

Making the programmer accessible to registers that are not conventional, such as PC and SP, makes it possible to enrich addressing modes. Thus, some modes can be implemented using others, such as, for example, absolute and relative modes with respectively indirect and indexed modes.

The trend has been towards multiplying addressing modes, making it possible to adapt to complex data structures such as those of high-level languages or application domains such as digital signal processing with its operations such as convolution or correlation. This wealth of modes facilitates the life of the assembly language programmer and makes it possible for the code to be compact during compilation. The counterpart is the complexity of the CU (Control Unit), one of the defects of the CISC approach (this will be covered in a future book by the author on microprocessors). The number of possibilities of machine codes depends on the number of instructions and associated addressing modes. Therefore, MC6809 had 59 instructions and 1,464 machine codes (Motorola 1981, 1983). A reverse tendency was that of reduced instruction set architectures (RISC, this will be covered in a future book by the author on microprocessors).

1.3. Conclusion

The following chapter focuses on the instruction set for a generic microprocessor by presenting the different instruction families and extensions in this set.

1В 1 In the context of a microprogrammed architecture (this will be covered in a future book by the author on microprocessors), it is sometimes called a macro-instruction to differentiate it from the micro-instruction, which is internal to the processor.

2В 2 Although these fields exist, they cannot be documented or can only be documented partially, as for MC6800 from Motorola.

3В 3 We can choose not to code the instruction (an uncoded instruction). This means that one bit is assigned to each of the possible operations. The gain lies in eliminating the logic of classic decoding and the corresponding stage in a pipelined architecture (this will be covered in a future book by the author on microprocessors). The immediate counterpart is an increase in its format.

4В 4 VAX for Virtual Addressed eXtended.

5В 5 For MicroController Unit, i.e. a microcontroller (cf. В§ V3-5.3).

6В 6 The mini-computer PDP-8 for Programmable Data Processor from DEC introduced in 1965 used this term.

7В 7 Vocabulary from DEC (1983).

8В 8 Here this means an immediate value following the instruction code that will serve as the address.

Конец ознакомительного фрагмента.

Текст предоставлен ООО «ЛитРес».

Прочитайте эту книгу целиком, купив полную легальную версию (https://www.litres.ru/philippe-darche/microprocessor-4/?lfrom=174836202) на ЛитРес.

Безопасно оплатить книгу можно банковской картой Visa, MasterCard, Maestro, со счета мобильного телефона, с платежного терминала, в салоне МТС или Связной, через PayPal, WebMoney, Яндекс.Деньги, QIWI Кошелек, бонусными картами или другим удобным Вам способом.