CMPE 401 - Computer Interfacing

Assignment #3

Model Solutions

 

  1. Briefly describe how the TCP segments travelling in the two opposite directions of a TCP connection interact. In your answer, explain what events can be triggered in the transmit direction when a new segment arrives at an end node in the receive direction.

 

A given TCP header contains a sequence number (a 32-bit number which is often initially randomly seeded by the sender, and indicates the byte number of the first data byte of the segment) as well as an acknowledgement number (another 32-bit number which indicates the sequence number the sender expects next from the receiver).  These fields are used after a sender and receiver exchange their sequence numbers (which are usually not synchronized), and are valid when the SYN and ACK flags are set.  A TCP header also contains a window field, the total number of bytes that may be transmitted without acknowledgement. 

 

When an end node receives a TCP packet, it checks the ACK number in the header.  If the number implies that bytes sent previously by the node have been safely received, then the retransmission copies of those bytes can be discarded.  On the other hand, if the ACK number implies that no further bytes were received (the number of unacknowledged bytes is at the window size), this may eventually cause a transmit time-out and hence a retransmission attempt.  ACK numbers may be transmitted on any packets going in the return direction, and need not be sent by themselves.  If packets are being lost or corrupted, an end node may send back a packet with a reduced window size.  The node on the other end acknowledges this by reducing its own window size. 

 

Transmission may be terminated by setting the FIN flag in the final transmitted packet.  A connection may be closed by sending a packet with both the FIN and ACK flags set (with the receiver sending a packet back with the same flags set).

 
  1. An autovectored 68000-class microcomputer has seven different interrupt priority levels (IPLs). What would be a reasonable mapping of external interrupts to these seven IPLs given the following external interrupt sources? (a) mouse movement and/or button pressed; (b) game console button(s) pressed; (c) new data packet received by the network interface card (NIC); (d) transmit data buffer empty in the NIC; (e) transmitted packet acknowledgement time-out in the NIC; (f) supply voltage monitor (e.g. power failure detected); (g) general-purpose hardware timer #1 (used for time slicing); (h) general-purpose hardware timer #2 (used for producing real-time control signals); and (i) general-purpose hardware timer #3 (available for other applications). Note that there are more than seven interrupt sources, so the interrupt service routines for some IPLs will be shared for multiple interrupt sources. Carefully justify your ranking of these interrupts. State your reasonable assumptions about system operation.

 

1)      Mouse / Game controller

Has the lowest priority, as these may be serviced infrequently without any noticeable delay to the user

 

2)      NIC transmit buffer empty / NIC transmit time out

Makes transfer more efficient by keeping the NIC busy and correctly transmitting data.

 

3)      NIC packet received

Ensure that NIC buffer does not overflow

 

4)      Timer (other)

May be used for time-critical (and small) functions

 

5)      Timer (time slice)

Ensures that the real time system apportions the time fairly

 

6)      Timer (real time)

Ensures that the system remains real time

 

7)      Supply voltage monitor

Should have highest priority as this is system critical, and may indicate an imminent system shut down.

 

The supply voltage monitor (f) should have the absolute highest priority (7) as this may indicate that power supply failure is imminent and any shut down procedures should be carried out.  The real time timer (h) should have the next highest priority (6) as this might be in use to satisfy hard real-time constraints (with rigid timing constraints, and tasks which must be initiated and completed within a certain time interval).  The mouse (a) and game controller (b) should together have the lowest priority (1) as these may be serviced relatively infrequently (in computer terms) without any noticeable delay to the user.  The priority of the remaining interrupt sources is flexible.


  1. What makes Direct Memory Access (DMA) such a fast method for transferring blocks of data between two regions in memory? What factors make DMA less efficient for transferring small blocks of data (compared to, say, using multiple microprocessor MOVE instructions).

 

Direct Memory Access avoids CPU overhead (in that the CPU does not need to decode addresses, retrieve data, decode another address and move it from the CPU to the final location (in addition to fetching and executing additional instructions).  DMA controllers are optimized to perform bulk data transfers, given starting source and destination addresses and the number of bytes to transfer.  Instead of taking several clock cycles to move a word, a DMAC might do this in one or two cycles instead.

 

However, DMA transfer requires the CPU to setup the transfer in the first place, and this comes with a certain amount of overhead.  Setting up DMA transfers on sufficiently small blocks of data may be less efficient than doing successive MOVEs.  Furthermore, DMA transfers signal their completion by interrupting the CPU.  The associated penalty (context switches, interrupt servicing time, etc.) will outweigh the benefits when transferring many small data blocks.

 

  1. Briefly explain what is meant by virtual memory. (If necessary, consult a reference on basic computer architecture, or consult an Internet tutorial article.) Then explain why at page boundaries, memory locations with adjacent physical addresses do not necessarily have adjacent virtual addresses. Why does this fact complicate the implementation of DMA in computer systems with virtual memory?

 

Virtual memory is the use of a large address space that defines possible memory that is much larger than the size of the installed RAM.  As it must store this “extra” memory on the hard drive (which is usually significantly slower to access than regular DRAM) it is referred to as virtual memory.  Inactive applications and data will be saved to the hard disk in the form of “pages” of consecutive bytes (e.g. 4 kB), and when accessed, will trigger a page fault, that swaps the requested page into RAM (often swapping out another to the hard disk).  Often, a memory management unit (MMU) provides the translation between virtual memory addresses and the physical ones they correspond to.

 

Virtual memory pages are allocated on the hard drive, one page at a time, and for various reasons (hard drive fragmentation, other allocated virtual memory pages, etc.) these pages are sometimes not physically adjacent, even if they are in the virtual memory space.  Thus DMA may be limited to transferring one (or a few) page(s) at a time, requiring accessing of the virtual memory table to find the physical disk locations of the adjacent pages.  It may also be the case that the page in RAM has been updated on the hard drive, requiring a “refresh” before data can be read.

 


  1. Briefly describe the operation of a ping-pong buffer. What would be a reasonable algorithm for determining when the two buffers should swap roles? Give pseudo-code that specifies your algorithm. What are the main constraints that must be respected in any such buffer control algorithm?

 

A (practical) double or ping-pong buffer is comprised of two equally-sized memory locations which alternate in their roles as a read buffer and a write buffer.  New data is written to the write buffer, while previous data is read from the read buffer.  When all of the data is read from the read buffer, the read buffer becomes the write buffer and vice versa, reversing the roles of the two buffers.

 

In order to swap the role of the two buffers:

·        check to see if the read buffer is all “read”

·        if so (and neither it nor the write buffer are empty to begin with) switch

 

This algorithm needs to ensure that there is no systematic mismatch in the read or write throughput, and that the buffers are sufficiently large in order to handle any mismatches (particularly the write buffer) and avoid buffer overflow.  It is also important to ensure that no data is lost while the buffers are switching roles.

 

Assume that initial read buffer A begins at memory location A_BEG and ends at A_END, with pointer MAX pointing to the last value written to this buffer, and pointer READ pointing to the value currently being read.  Initial write buffer B begins at memory location B_BEG and ends at B_END, with pointer WRITE pointing to the memory location to be written to next.  This code snippet runs following a read operation, and initialization is handled elsewhere.  Alternately, and perhaps safer, the buffer could run as its own process, giving advance warning to the read and write processes about an impending swap in the buffers, only performing the swap once the other two processes are ready.

 

/* Ping pong buffer pseudocode */

BEGIN

MAX at A_BEG?                       /* Read buffer empty? */

NO:   READ at A_END or MAX?         /* Finished reading? */

      YES:  WRITE at B_BEG?         /* Write buffer empty? */

               YES:  END

               NO:   /* FLIP BUFFERS */

                     MAX = WRITE

                     READ = B_BEG

                     WRITE = A_BEG

                     SWAP values in A_BEG and B_BEG

                     SWAP values in A_END and B_END

                     END

         NO:   END

   YES:  WRITE at B_BEG?               /* Should only see at start*/

         YES:  END

NO:   (Copy of NO condition buffer flipping code above)

   END


  1. Consult the on-line documentation for the TPU (available by following the link from the course homepage) to determine how the "Pulse Width Modulation" built-in function works (function code $9). Briefly explain, in your own words, the capabilities of this function. Your explanation should describe what is meant by terms "pulse width modulation" and "duty cycle".

 

Pulse width refers to the amount of time τ that an electrical signal is high during one cycle of a square wave with period T (see Fig. 1)  Typically, pulse width is used in the context of duty cycle, the percentage of time that the square wave is high:

 

 

Pulse width modulation varies the pulse width while maintaining a fixed period.  PWM can be used to encode sensor readings (e.g. an accelerometer), or motion commands (e.g. remote controlled airplanes and the use of PPM—Pulse Position Modulation, a form of PWM).  PWM may also be used to control power delivery (e.g. for a motor or for lights) allowing (possibly) fine control over average output power without having to resort to analog electronics.

 

While the initialization of the TPU is not insignificant, the actual control of the individual TPU channels to provide PWM output is fairly straightforward.  $9 must be assigned to the correct 4 bits of the appropriate Channel Function Select Register (CFSR) to enable a particular channel to output PWM.  In the parameter RAM for the particular TPU channel W, two 16-bit registers PWMHI (at TPU offset $1W4), and PWMPER (at TPU offset $1W6) control the pulse width and period of the square wave, respectively.  The 16-bit values written to these register are the number of TPU clocks, such that PWMHI < PWMPER.