c©2004-2010 . Lumetta. All rights reserved. 1
ECE391: Computer Systems Engineering Lecture Notes Set 0
Copyright By PowCoder代写 加微信 powcoder
Review Material
This set of notes reviews material that you have probably already seen in ECE190 or ECE290 (or CS225). If you took
neither ECE190 nor CS225, some of it may be new to you; the TAs might also talk about some of this material in
the first couple of discussion sections, and both MP1 and MP2 will require you to make use of it. Regardless of your
previous experience, you may want to scan the list of terms at the end of these notes and review the definitions for any
terms that seem unclear to you. In order to make the notes more useful as a reference, definitions are highlighted with
boldface, and italicization emphasizes pitfalls.
The notes begin with a review of how information is represented in modern digital computers, highlighting the use
of memory addresses as pointers to simplify the representation of complex information types. The next topic is the
systematic decomposition of tasks into subtasks that can be executed by a computer, and an example based on a
pointer-based data structure. Moving on to high-level languages, and particularly the C language, the notes continue
with a review of type and variable declarations in C as well as the use of structures, arrays, and new types. The
next topic is C operators, with some discussion of the more subtle points involved in their use. After revisiting the
decomposition example as written in C, the notes discuss implicit and explicit conversions between types. Finally, the
notes conclude with a review of C’s preprocessor. We deliberately omit the basics of C syntax as well as descriptions
of C conditional (if/else and switch) and iteration (while, do, and for loops) statements.
Representation as Bits
Modern digital computers represent all information as sets of binary digits, i.e., 0s and 1s, or bits. Whether you are
representing something as simple as an integer or as complex as an undergraduate thesis, the data are simply a bunch
of 0s and 1s inside a computer. For any given type of information, a human selects a data type for the information.
A data type (often called just a type) consists of both a size in bits and a representation, such as the 2’s complement
representation for signed integers, or the ASCII representation for English text. A representation is a way of encoding
the things being represented as a set of bits, with each bit pattern corresponding to a unique object or thing.
In general, computers do not interpret the bits that they store. A typical instruction set architecture (ISA) supports a
handful of data types in hardware in the sense that it provides hardware support for operations on those data types.
Most modern arithmetic logic units (ALUs), for example, support addition and subtraction of both unsigned and
2’s complement representations, with the specific data type (such as 16- or 64-bit 2’s complement) depending on the
ISA. Data types and operations not supported by the ISA must be handled in software using a small set of primitive
operations, which form the instructions available in the ISA. Instructions usually include data movement instructions
such as loads and stores and control instructions such as branches and subroutine calls in addition to operations.
Pointers and Data Structures
One particularly important type of information is memory addresses. Imagine that we have stored some bits represent-
ing the number 42 at location 0100100100010100 in a computer’s memory. In order to retrieve our stored number,
or rather the bits representing it, we must provide the memory with the bits corresponding to the memory location, in
this case 0100100100010100. The representation of a memory address as bits is thus straightforward: we simply use
the bits that must be provided to the memory in order to retrieve the desired data as the representation for that memory
address. Unlike most other types of information, no translation process is necessary; we represent a bunch of bits with
a bunch of bits. We might thus think of the bits 0100100100010100 as a pointer to the number 42. They point to our
stored number in the sense that the memory, when provided with the pointer, produces the stored number.
It is important to recognize, however, that a pointer is just a bunch
of bits, just like any other representation used by a computer. In
particular, we can choose to interpret the bits making up a pointer as
an unsigned integer, which provides us with a way of ordering the
locations in a memory’s address space, as shown to the right for a
memory consisting of 232 locations holding 16 bits each, i.e., with an
addressability of 16 bits.
16 bits in each location
(16−bit addressability)
address space
locations in a 32−bit
4,294,967,295
2 c©2004-2010 . Lumetta. All rights reserved.
The induced ordering is useful when the representation for some type of in-
formation requires more bits than the addressability of the memory. Imagine
that you are charged with selecting a representation for the birth and hiring
dates of all employees of your company in a memory with 16-bit addressabil-
ity. Given a reasonable set of assumptions about the range of possible values,
representing two dates with only 16 bits is quite challenging. Instead, you
might decide to use six memory locations for each person, representing each
person with 2’s complement integers for the day, month, and year of the two
recorded dates. An example appears to the right. Such a multi-location repre-
sentation is often called a data structure, because the information represented
is made up of several components, or fields, each of which has a data type. In
this case, all of the fields are 16-bit 2’s complement integers, but the fields of
a data structure need not in general have the same type.
0000 0111 1101 0100
0000 0000 0000 1000
0000 0000 0001 0000
0000 0111 1011 1110
0000 0000 0000 0001
0000 0000 0001 0110
(8 = August)
(1 = January)
In the example above, the value 1,234,560 (i.e., the bit pattern 00000000000100101101011010000000) is a pointer to
the employee structure, and all fields of the data structure reside at fixed offsets from this pointer. To find the hiring
month, for example, one adds four to the pointer and retrieves the value from the resulting memory address (i.e., treat-
ing the sum again as a pointer).
Multiple instances of a certain type are often represented as arrays. Again
using the ordering induced by treating memory addresses as unsigned
integers, the bits for each element of the array are simply laid out se-
quentially in memory, with each element occupying whatever number of
memory locations is necessary for the data type. We refer to this number
as the size of the type, and (usually) measure it in terms of the address-
ability of the memory system. Given the address of the first element of
an array, we can easily calculate the address of any element by simply
adding a multiple of the size of the type. For convenience, we number
array elements starting with 0, allowing us to use the product of the array
index and the type size as the offset for any given element. All array
elements must be of the same size in order for this calculation to work
properly. In the example shown to the right, we find element 2 by adding
2× 6 to 1,234,560. The result, 1,234,572, is a pointer to element 2 of the
array. We can also think of the pointer 1,234,572 as a pointer to an array
with two fewer elements than the original array.
The duality between pointers and arrays, by which any pointer can be
treated as an array, and any array can be treated as a pointer, is both useful
and a potential source of confusion. If, for example, you create an array
of ten of our double-date structures, and write code that takes a pointer
to the array of ten and accesses the eleventh (element 10), your code will
proceed to read garbage bits from the memory. Adding 10 × 6 to the
0000 0000 0001 0110
0000 0000 0000 0001
0000 0111 1011 1110
0000 0000 0000 1000
0000 0000 0001 0000
0000 0000 0000 0111
0000 0111 1101 0100
0000 0000 0000 1101
0000 0111 1100 1011
0000 0000 0001 0011
0000 0000 0000 1001
0000 0000 0001 0010
0000 0111 1101 1110
0000 0000 0000 0011
0000 0111 1100 0000
0000 0000 0000 0101
0000 0000 0000 0110
0000 0111 1101 0101
1,234,560 (22)
(1 = January)
(8 = August)
(7 = July)
(9 = September)
(3 = March)
(6 = June)
pointer to element 0 does produce a valid memory address, but neither the contents of that address nor those of the
subsequent five addresses were intended to be a double-date structure. With any pointer (i.e., memory address), your
program must keep track of the type of the data to which the pointer points. With a pointer to an array, your code must
also keep track of the size of the array. To a computer, bits are just bits.
Multidimensional arrays are usually handled by thinking of each of the lower dimensions in the array as a new type
of data. For example, let’s say that we want to create an array of our double-date structures with seven rows and five
columns, as shown in the following figure. We begin by thinking about an array of five double-date structures. Each
row in our two-dimensional array is simply an array of five double-date structures. Our entire two dimensional array
is then an array of seven of the arrays of five. When we lay it out in memory, the arrays of five are again laid out
consecutively.
c©2004-2010 . Lumetta. All rights reserved. 3
logical view:
an array of
double−date structures
with 7 rows
and 5 columns
second array of 5
first array of 5
memory view:
35 consecutive
double−date structures
intermediate view:
an array of 7
arrays of 5
double−date structures
row 4, column 3
How do we find an element in our two-dimensional array? Let’s say that we want to access row 4 and column 3. The
size of the array of five is 5 × 6 = 30, and we are looking for row 4, so we multiply 4 × 30 and add it to the pointer
to the start of the array to find a pointer to row 4. We then multiply 3 × 6 and add it to the pointer to row 4 to obtain a
pointer to the desired array element. As you may have already observed, the duality between arrays and pointers also
holds for multi-dimensional arrays: we can choose to view our two-dimensional array as an one-dimensional array of
35 structures if it is useful or convenient to do so.
Arrays of Pointers
As mentioned earlier, a pointer is simply a type of information. In practice,
it is often useful to associate the type of information to which a pointer
points with the pointer itself, but this association is purely an abstraction and
has no effect on the bits used to represent the pointer. However, mentally
distinguishing a pointer to an integer from a pointer to one of the double-
date data structures from our running examples can help when discussing
our next step: a pointer may point to a pointer, which may in turn point to
another pointer, and so forth.
As a simple example, rather than building an array of our double-date struc-
tures in memory, we might instead build an array of pointers to double-date
structures, as shown to the right. The upper block in the figure shows the
first two pointers in our array of pointers; each pointer occupies 32 bits,
or two memory locations. The lower block in the figure shows the first
structure referenced by the array; the address of this structure is stored as
element 0 in our array of pointers. The middle block in the figure shows
the second structure referenced by the array, i.e., the structure to which el-
ement 1 of the array points. Given a pointer—227,660—to the array, we
obtain a pointer to element 1 by adding 2, the size of a pointer, to the array
pointer. The data at that memory address are then the address of the desired
structure, in this case the pointer 765,432.
What is the difference between using an array of pointers to structures and
using an array of structures? With an array of structures, finding the ad-
dress of any desired element is easy, requiring only a multiplication and an
0000 0111 1101 0100
0000 0000 0000 1000
0000 0000 0001 0110
0000 0111 1011 1110
0000 0000 0000 0001
0000 0000 0001 0000
0000 0111 1101 1110
0000 0000 0000 1001
0000 0000 0001 0011
0000 0111 1100 1011
0000 0000 0000 0111
0000 0000 0000 1101
0000 0000 0000 1011
1010 1101 1111 1000
0000 0000 0001 0010
(1,234,560)
(7 = July)
(9 = September)
(1 = January)
(8 = August)
(2004)1,234,565
1101 0110 1000 0000
addition. Using an array of pointers to structures introduces another memory access to retrieve the structure pointer
from the array. However, if we want to move elements around within the array, or want to be able to have the same
structure appear more than once in the array, using an array of pointers makes our task much easier, as moving and
copying pointers is easier than moving and copying whole data structures, particularly if the data structures are large.
Similarly, using an array of pointers allows us to use a special value (usually 0) to indicate that some elements do not
exist, which may reduce the amount of memory needed to store an array for which the size changes while the program
4 c©2004-2010 . Lumetta. All rights reserved.
Pointers within Data Structures
Just as we can form arrays of pointers, we can also include pointers as fields within data struc-
tures. For example, we can extend our double-date structure by appending a field that points
to another double-date structure, as shown to the right. This new structure can then be linked
together, from one to the next, to form a list of structures representing the birth and hiring dates
for all employees of a company. We call such a structure a linked list, with the pointer field
forming the link between each element in the list and the subsequent element. A single pointer
then suffices to indicate the location of the start of the list, and a special value (again, 0) is used
to indicate the end of the list.
The figure below illustrates a linked list of two employees. The upper part of the figure is
next structure
pointer to
hiring year
hiring month
hiring day
birth year
birth month
the logical list structure, and the lower part is a possible organization in memory. For this figure, we have deliberately
changed both the addresses and bits for each memory location into hexadecimal form. Hexadecimal notation is easier
for humans to parse and remember than is binary notation. However, use of hexadecimal is purely a notational
convenience and does not change the bits actually stored in a computer.
0x0003794D
0x0003794C 0x0012D620
0x0012D621
0x0012D622
0x0012D623
0x0012D624
0x0012D625
0x0012D626
0x0012D627 0x000BADFF
0x000BADFE
0x000BADFD
0x000BADFC
0x000BADFB
0x000BADFA
0x000BADF9
0x000BADF8
0xD620 0x0016
0x000B 0x0000
(end of list)
22head of list
(0x0012D620)
(1 = January)
(8 = August)
(0x000BADF8) (0x00000000)
(9 = September)
(7 = July)
What is the difference between using a linked list and using an array of pointers? A linked list requires only one pointer
per element in the list, plus one extra for the list head, and does not require a programmer to guess the maximum size
of the list in advance. In contrast, an array of pointers contains a fixed number of pointers; this number must be chosen
in advance, and must be large enough for all executions of the program, even if most executions require far fewer
list elements than this theoretical maximum. The array itself can be resized dynamically, but doing so requires extra
memory accesses and copying. The speed of access in an array is its primary advantage. For comparison, getting to
the middle of a list means reading all of the pointers from the head of the list to the desired element. More sophisti-
cated data structures using multiple pointers to provide more attractive tradeoffs between space and operation speed
are possible; you will see some of these in ECE391, but are not assumed to have already done so.
Systematic Decomposition
We are now ready to shift gears and talk about the process of turning a specification for a program into a working
program. Essentially, given a well-defined task expressed at some suitably high level of abstraction, we want to be
able to systematically transform the task into subtasks that can be executed by a computer. We do so by repeatedly
breaking each task into subtasks until we reach the desired level, i.e., until each of the remaining tasks requires only
a machine instruction or two. The name for this process is systematic decomposition, and the ECE190 textbook by
Patt and Patel1 provides a detailed introduction to the ideas; the basics are replicated here for review purposes.
1Yale N. Patt, . Patel, Introduction to Computing Systems: from Bits & Gates to C & Beyond, second edition, McGraw Hill, ,
, 2004, ISBN 0-07-246750-9.
c©2004-2010 . Lumetta. All rights reserved. 5
sequential
condition hold?
subtask when
condition holds
subtask when
condition does
conditional
one iteration
subtask for
are we done
iterating?
When writing a program, it is often helpful to get out a sheet of paper and draw a few pictures of the data structures
before trying to write code. Similarly, it is often useful to explicitly draw the organization of the code, which is where
systematic decomposition comes into play. Begin by drawing a single box that implements the entire task. Next,
repeatedly select a box that cannot be implemented with a single machine instruction and break it down into smaller
tasks using one of the three constructions shown above: sequential, iterative, or conditional. Some tasks require a se-
quence of subtasks; for these, we use the sequential construction, breaking the original task into two or more subtasks.
Some tasks require repetition of a particular subtask. These make use of the iterative construction; determining the
condition for deciding when the iterative process should end is critical to using such a construction. Finally, some tasks
divide into two (or possibly more) subtasks based on some condition. To make use of the conditional construction,
this test must be stated explicitly, and the steps for each outcome clearly stated.
Example: Decomposing Linked List Removal
As an example, let’s decompose the
task of removing one of our double-
date data structures from a linked
list. For this task, we are given two
input variables. The variable head
holds a pointer to the list head, and
the variable elt holds a pointer to
the element to be removed from the
list. The variable names represent
the addresses at which these values
are stored. Thus, at the register
(second iteration) (third iteration) (fourth iteration) (fifth iteration) (last iteration)
(fifth iteration)(fourth iteration)(third iteratio
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com