Wednesday, December 2, 2009

William Stallings Computer Organization and Architecture

Chapter 2
Computer Evolution and
Performance
Key Points



• The evolution of computers has been characterized by increasing processor speed, decreasing component size, increasing memory size and increasing I/O capacity and speed
• Processor speed is as a result of shrinking factor in the processor components; reducing the distance between the components hence, increasing speed. True cause is the organization of the processor e.g. pipelining and parallel execution techniques
• Critical issue here is the balancing of the performance of the various elements

A Brief History of Computers
• First generation – vacuum tubes
 ENIAC The
 Von Neumann Machine
 Commercial computers
• Second generation – Transistors
 The IBM 7094
 Third generation – Integrated Circuits
 Later generations

ENIAC - background
• Electronic Numerical Integrator And Computer
• By John Presper Eckert and Prof. John Mauchly at the
• University of Pennsylvania
• World’s first general-purpose electronic digital computer
• Started 1943
• Trajectory tables for weapons
• Finished 1946
 Too late for war effort
• Used until 1955

ENIAC - details
• Decimal (not binary)
• 20 accumulators, each capable of holding 10 digits each
• Programmed manually by switches
• 8,000 vacuum tubes
• 30 tons
• 15,000 square feet
• 140 kW of power consumption
• 5,000 additions per second

Von Neumann/Turing
• 1945-first publication of the idea; the EDVAC (Electronic Discrete Variable Computer)
• The manual programming was too tedious
• Stored Program concept by John Von Neumann; Alan Turing developed the idea at around the same time
• Main memory storing programs and data -a for suitable for storing in memory alongside data
• ALU operating on binary data
• Control unit interpreting instructions from memory and executing
• Input and output equipment operated by control unit
• Work on the computer begun at the Princeton Institute for Advanced Studies. The computer was named, IAS
• Computer and was completed in 1952
• This is the prototype of all subsequent general-purpose computer

Von Neumann/Turing Components
• A main memory that stores both data and instructions
• An ALU (Arithmetic and Logic Unit) capable of operating on binary data
• A control Unit which interprets the instructions in memory an causes them to be executed
• Input and output (I/O) equipment operated by the control unit

Structure of von Neumann


IAS - details
• 1000 storage locations (words) of 40 bits each; both data and instructions are stored here
• Everything must be in Binary number
• Each number is represented by a sign bit and a 39- bit value (see figure 2.2 on page 19 for the William’s book)
• 2 instructions per word of 20 bits each


IAS - details
• Set of registers (storage in CPU)
• Memory Buffer Register (MBR) contains a word to be stored in memory or is used to receive word from memory
• Memory Address Register(MAR) – specifies the address in memory of the word to be written from or read into the MBR
• Instruction Register(IR) – contains the 8-bit opcode instruction being executed
• Instruction Buffer Register (IBR) – employed to hold temporarily the right-hand instruction from a word memory
• Program Counter (PC)- contains the address of the next instruction-pair to be fetched from memory
• Accumulator (AC) and Multiplier Quotient (MQ) – employed to hold temporarily operands and results of ALU operations; e.g. a*b=c(80bits) so the most significant 40 bits are stored in the
• AC and the least significant stored in MQ

Structure of IAS - detail

Commercial Computers
• 1947 -Eckert-Mauchly Computer Corporation
• UNIVAC I (Universal Automatic Computer)
• US Bureau of Census 1950 calculations
• Became part of Sperry-Rand Corporation
• Late 1950s -UNIVAC II
• Faster
• More memory

• IBM
• Punched-card processing equipment
• 1953 - the 701
 IBM’s first stored program computer
 What does IBM stand for?
 Scientific calculations
• 1955 - the 702
 Business applications
• Lead to 700/7000 series

Transistors
• Replaced vacuum tubes
• Smaller
• Cheaper
• Less heat dissipation
• Solid State device
• Made from Silicon (Sand)
• Invented 1947 at Bell Labs
• William Shockley et al.

Transistor Based Computers
• Second generation machines
• NCR (?) & RCA (?) produced small transistor machines
• IBM 7000
• DEC -1957
 Produced PDP-1

Microelectronics
• Literally - “small electronics”
• A computer is made up of gates, memory cells and interconnections
• These can be manufactured on a semiconductor

Generations of Computer
• Vacuum tube -1946-1957
• Transistor -1958-1964
• Small scale integration -1965 on
 Up to 100 devices on a chip
• Medium scale integration -to 1971
 100-3,000 devices on a chip
• Large scale integration -1971-1977
 3,000 -100,000 devices on a chip
• Very large scale integration -1978 to date
 100,000 -100,000,000 devices on a chip
• Ultra large scale integration
 Over 100,000,000 devices on a chip

Moore’s Law
• Increased density of components on chip
• Gordon Moore - cofounder of Intel
• Number of transistors on a chip, will double every year
 Since 1970’s development has slowed a little
• Number of transistors doubles every 18 months
• Cost of a chip has remained almost unchanged
• Higher packing density means shorter electrical paths, giving higher performance
• Smaller size gives increased flexibility
• Reduced power and cooling requirements
• Fewer interconnections increases reliability

Growth in CPU Transistor Count



IBM 360 series
• 1964
• Replaced (& not compatible with) 7000 series
• First planned “family” of computers
 Similar or identical instruction sets
 Similar or identical O/S
 Increasing speed
 Increasing number of I/O ports (i.e. more terminals)
 Increased memory size
 Increased cost
• Multiplexed switch structure

DEC PDP-8
• 1964
• First minicomputer (after miniskirt!)
• Did not need air conditioned room
• Small enough to sit on a lab bench
• $16,000
 $100k+ for IBM 360
• Embedded applications & OEM
• BUS STRUCTURE


DEC -PDP-8 Bus Structure

Intel
• 1971 - 4004
 First microprocessor
 All CPU components on a single chip
 4 bit
• Followed in 1972 by 8008
 8 bit
 Both designed for specific applications
• z1974 - 8080
 Intel’s first general purpose microprocessor

Designing for Performance
• The cost of computers continue to drop while the performance and capacity continue to rise
• However, the basic building blocks for today’s computers are virtually the same as those of the IAS computer from over 50 years ago!
• The key idea is therefore the techniques for squeezing performance out of the material.

Microprocessor Speed-
Speeding it up
• Pipelining
• On board cache
• On board L1 & L2 cache
• Branch prediction
• Data flow analysis
• Speculative execution

Performance Mismatch
• Processor speed increased
• Memory capacity increased
• Memory speed lags behind processor speed

Solutions
• Increase number of bits retrieved at one time
 Make DRAM “wider” rather than “deeper”
• Change DRAM interface
 Cache
• Reduce frequency of memory access
 More complex cache and cache on chip
• Increase interconnection bandwidth
 High speed buses
 Hierarchy of buses

Internet Resources
• http://www.intel.com/
 Search for the Intel Museum
• http://www.ibm.com
• http://www.dec.com
• Charles Babbage Institute
• PowerPC
• Intel Developer Home

Tuesday, December 1, 2009

ICS 113: Programming


Structures in C



Introduction to structures
n Arrays are data structures whose elements are of the
same type.
n Structure is “a data structure ” in which the individual
elements can di ffer in type.
n A structure is a data type that consists of a collection of
several variables stored together. A structure can also be
referred to as a record.
n The individual structure elements are known as
elements.

Defining a structure


A structure must be def ined in terms of its indi vidual
members. In general terms, a structure may be def ined
as:
struct tag{
member 1;
member 2;
member 3;
........
member m;
};


Structure members




The individual members can be ordinary var iables,
pointers, arrays or other structures.

The member names wi thin a particular structure must be
distinct from one another, though a member name can be
the same as the name of a variable that is defined
outside the structure.

Individual members cannot be initiali zed within a
structure type declarati on.

A storage class cannot be assigned to an individualmember.

Declaring a structure
n Once the composition of the structure has been defined, individual
structure type variables can be declared as follows:
storage_class struct tag variable1, variable2, variable n;
– Storage_class is an optional storage class specifier
e.g. static, external e.t.c.
– struct is a required keyword,
– tag is the name that appeared in the structure
declaration and
– variable1 to variable n are structure variables of type
tag.

Example 1

struct account{
int acct_no;
char acct_type;
char name[80];
float balance;

};


We can now declare the structure variables customer1
and customer2 as follows:
struct account customer1, customer2;


Thus, customer1 and customer2 are variables of type
account. In other word s, customer1 and customer2 are
structure-type variables whose composition i s identified
by the tag account.

Combining structure and variable declarations

storage_class struct tag{

member 1;

member 2;

member 3;

.........


member m;
}variable1, variable2, ..., variable n;


The tag is optional in this situation.

Example 2



struct account{ struct {
int acct_no; int acct_no;
char acct_type; char acct_type;
char name[80]; char name[80];
float balance; float balance;

} customer1, customer2; } customer1, customer2;


Case 1 and 2 serve the same purpose


Embedded structures




A structure variable can also be a def ined as a member
of another structure.

In such situations, the declaration of the embedded
structure must appear bef ore the declaration of the outer
structure.

Example 3

struct date{

int month;

int day;

int year;
};

struct {

int acct_no;

char acct_type;

char name[80];

float balance;

struct date lastpayment;
} customer1, customer2;


Structure initialization
n The members of a structure can be assigned initial
values in much the same manner as the elements of an
array.
n The initial values must appear in the order in wh ich they
will be assigned to thei r corresponding structure
members, enclosed in braces and separated by
commas. The general form is:
storage_class struct tag variable ={value1,
value2, value3, …., valuem};
n N.B. A structure variable, like an array, can be initialized
only if its storage class is either external or static.

Example 4
struct date{
int month;
int day;
int year;
};
struct {
int acct_no;
char acct_type;
char name[80];
float balance;
struct date lastpayment;
};
static struct account customer = {987654, ‘S’, “Will Obongo”, 102,589.30, 8, 12,
2005}

Array of structures



It is also possible to define anarray of structures, i.e. an
array in which each element is
a structure.
struct date{

int month;

int day;

int year;
};
struct {

int acct_no;

char acct_type;

char name[80];

float balance;

struct date lastpayment;
}customer[100];


In this declaration,
customer is a 100
element array ofstructures.Hence, each
element of customer is a
separate structure of typeaccount i.e. each element
of customer represents anindividual customer
record.

Initializing an array of structures


struct date{
char name[80];
int month;
int day;
int year;

};

static struct date bday[]={
{"Amy", 12, 30, 73},
{"Gail", 5, 13, 66},
{"Marc", 7, 15, 72},
{"Maria", 5 29, 67}
};

struct date{
char name[80];
int month;
int day;
int year;

};

static struct date bday[]={
"Amy", 12, 30, 73,
"Gail", 5, 13, 66,
"Marc", 7, 15, 72,
"Maria", 5 29, 67
};


Naming members




Remember that each structure is a sel f contained entity
with respect to member def initions.

Thus, the same member name can be used i n different
structures to represent di fferent data, i.e. the scope of a
member name is conf ined to the particular structure
within which it is def ined.

Processing a structure



The members of a structure are usually processed
individually, as separate entities. Theref ore, we can
access the individual members by writin g:
variable.member


Where variable refers to the name of a structure -type
variable, and member refers to the name of a member
within the structure.

Notice the period (.) that separates the variable name
from the member name. T his period is an operator; it is a
member of the highest precedence group, and its
associativity is left to right.

Example 5



struct date{ •
customer.acct_no;
int month; •
date.month;


customer.balance;
int day;

int year;
};
struct {

int acct_no;

char acct_type;

char name[80];

float balance;

struct date lastpayment;
}customer;


(.) operator




Since this operator is a member of the highest
precedence group, this operator wil l take precedence
over the unary operators as well as the various
arithmetic, relational, l ogical and assignment operators.

Thus ++variable.member = ++(variable.member) and
&variable.member = &(variable.member)

(.) expressions




More complex expressions invol ving the repeated use of
the period operator may also be written.

For example, if a structure member is itself a structure,
then a member of the embedded structure can be
accessed by writing
variable.member.submember


Where member refers to the name of the member within
the outer structure, and submember refers to the name of
the member withinn the embedded structure.

Example 6

struct date{
int month;
int day;
int year;

}; •
customer.lastpayment.month

struct { •
++customer.lastpayment.month
int acct_no; •
customer.name[2]
char acct_type; •
&customer.name[2]
char name[80];
float balance;
struct date lastpayment;

}customer;


(.) with arrays of structures




The use of the period operator can be extended to arrays of
structures, by writing:
array[expression].member

where array refers to the array name, and array[expression] refers
to an individual array element (a structure variable). Therefore
array[expression].member will refer to a specific member within a
particular structure.


Example 7

struct date{
int month;
int day;
int year;

}; •
Customer[13].acct_no


Customer[13].balance
struct {


Customer[13].name
int acct_no;


Customer[13].name[6]
char acct_type;


Customer[13].lastpayment.month
char name[80];


++Customer[13].lastpayment.day

float balance;
struct date lastpayment;
}customer[100];


Processing structure members



Structure members can be processed in the same
manner as ordinary va riables of the same data type.

Single-valued structure members can appear in
expressions, they can be passed to functions, and they
can be returned f rom functions as though they were
ordinary single-valued variables.

Complex structure members are processed i n the same
way as ordinary data items of that same type. E.g. a
structure member that is an array can be processed in
the same manner as an ordinary array, and with the
same restrictions.

User defined data types (typedef)



The typedef feature allows users to define new data-
types that are equivale nt to existing data types.

Once a user-defined data type has been established,
then new variables, arr ays, structures etc can be
declared in terms of thi s new data type.

typedef



In general terms, a new data type is def ined as:
typedef type new-type
where type refers to an existing data type (either a
standard data type, or previous user -defined data type),
and new-type refers to the new user -defined data type.


It should be understood however, that the new data
type will be new in name only. In reality, this new data
type will not be fundamentally different f rom one of the
standard data types.

typedef int age;

thus

age male, female;

Is equivalent to

int male, female;

Example 8

The following declarations:


typedef float height[100];

Height men, women;
define height as a 100-element floating
point array type, hence men and
women are 100 element floating point
arrays. Another way to express this is


typedef float height;

height men[100], women[100];

typedef and structures




The typedef feature is particularly convenient when defining
structures, since it eliminates the need to repeatedly write struct tag
whenever a structure is referenced.

In addition, the name given to a user-defined structure type often
suggests the purpose of the structure within the program.

In general terms, a user defined structure type can be written as:
typedef struct{
member1;
member2;
.......
membern;


}new_type;


Example 9


typedef struct {
int acct_no;
char acct_type;
char name[80];
float balance;

}record;

record oldcustomer,
newcustomer;


typedef struct{
int month;
int day;
int year;

}date;

typedef struct {
int acct_no;
char acct_type;
char name[80];
float balance;
date lastpayment;

}record;

record customer[100];


Example 10



typedef struct{
int month;
int day;
int year;

}date;

typedef struct {
int acct_no;
char acct_type;
char name[80];
float balance;
date lastpayment;

}record[100];

record customer;

typedef struct{
int month;
int day;
int year;

}date;

typedef struct {
int acct_no;
char acct_type;
char name[80];
float balance;
date lastpayment;

}customer [100];


Structures and pointers



The beginning address of a structure can be accessed in the
same manner as any other address, through the use of the
address (&) operator.

Thus if variable represents a structure-type variable, then
&variable represents the starting address of that variable.

Moreover, we can declare a pointer vari able for a structure by
writing
type *ptvar;
where type is a data type that identifies the composition of the
structure and ptvar represents the name of the pointer variable.


We can then assign the beginning address of a structure variable
to this pointer by writing
ptvar = &variable;


Example 11


typedef struct {
int acct_no;
char acct_type;
char name[80];
float balance;

}account;

account customer, *pc;
pc = &customer;

typedef struct {
int acct_no;
char acct_type;
char name[80];
float balance;

}customer, *pc;

pc = &customer;



Accessing individual members using
pointers



An individual structure member can be accessed in
terms of its corresponding pointer variable by writin g
ptvar->member


ptvar refers to a structure -type pointer variable and the
operator -> is comparable to the period (.) operator. Thus
the expression ptvar->member is equivalent to writing
variable.member where variable is a structure -type
variable.

The operator falls into the highest precedence group, like
the period operator and its associativity is also left to
right.

(.) and ->
n The –> operator and the period operator can be
combined to access a submember within a structure.
Hence the submember can be accessed by writing
ptvar->member.submember
n Similarly, the -> operator can be used to access an
element of an array that is a member of a structure..
ptvar->member[expression]

Example 12



customer.acct_no

pc->acct_no

(*pc).acct_no
typedef struct{
int month;
int day;
int year;

}date;

typedef struct {
int acct_no;
char acct_type;
char name[80];
float balance;
date lastpayment;

}customer, *pc=&customer;


The parentheses are
required in the last
expression because
the period operator
has a higher
precedence than the
*.


Pointers as structure members




A structure can also include one or more pointers
as members.

If ptmember is a pointer and a member of
variable, then *variable.ptmember will access the
value to which ptmember points.

Passing structures to functions



Individual structure members can be passed to a
function as arguments in the function call, and a
single structure member can be returned via the
return statement.

Example 13


float adjust(char name[], int acct_no,
float balance)
main(){
typedef struct{
int month;
int day;
int year;
}date;
typedef struct {
int acct_no;
char acct_type;
char name[80];
float balance;
date lastpayment;
}customer;

customer.balance =
adjust(customer.name,
customer.acct_no,
customer.balance);

}

float adjust(char name[],
int acct_no, float
balance)

{
float newbalance;
newbalance=.....;
return(newbalance);

}


Passing structures to functions



A complete structure can be transferred to a function by
passing a structure -type pointer as an argument.

However, we must use explicit pointer notation to
represent a structure that is passed as an argument.

A structure passed in this manner is passed by reference
rather than by value.

Example 12

#include
typedef struct {

void adjust(record *pt)

char *name;

{

char acct_type;
int acct_no; pt->name="John
float balance; W.";


}record;

pt->acct_type='S';

void adjust(record *pt);

pt>
acct_no=34569;

main()
{ pt->balance=0.0;
static record cust =

}

{"smith",'C',333,34765};
printf("%s %c %d %.2f\n", cust.name,


cust.acct_type, cust.acct_no,
cust.balance);
adjust(&cust);
printf("%s %c %d %.2f\n", cust.name,


cust.acct_type, cust.acct_no,
cust.balance)
}