Transcript 1million pixels

Today's Agenda
What is Computer Architecture?
What is Computer Organization?
Brief history of Computers
Introduction to Binary Number Systems
Layers of Abstraction: from application
program to execution of program
High Level
Language
main() {
int i,b,c,a[10];
for (i=0; i<10; i++)…
a[2] = b + c*i;
}
Compiler
ISA
…
lw r2, mem[r7]
add r3, r4, r2
st r3, mem[r8]
Assembler
Where ISA is positioned in entire Abstraction
layers
Application
Operating
System
Compiler
Instr Set Proc.
Firmware
I/O system
Datapath & Control
Digital Design
Circuit Design
Layout
Instruction Set
Architecture
Architecture
 Architecture is those attributes visible to the programmer
 Instruction set
 Number of bits used for data representation
 I/O mechanisms
 Memory addressing techniques
 Architecture Question:
 Is there a multiply/division instruction available?
Organization
 Organization is how features are implemented
 Control signals
 Interfaces between computer and peripherals
 Memory technology used
 Organization Question:
 Is multiplication is implemented by separate hardware or is it
done by repeated addition?
Architecture & Organization
 All Intel x86 family share the same basic architecture
 The IBM System/360 family share the same basic architecture
 This gives code compatibility
 At least backwards
 Organization differs between different versions
Example Processor: LC3
 Addressability is 16 bit – 216 address space
 8 Registers each 16 bit – it requires 3 bits to represent each
register
 Opcode is 4 bit long – 16 different instructions can be there
 Addressing Modes
 Example instruction:
 ADD R3,R4,R2
 0001 011 010 000 001 – machine equivalent of ADD
instruction
History of Computers
First Generation Computer: Vacuum Tubes
 Decimal machine rather
than a binary machine
 Mainly used for large
calculations.
 It had to be programmed
manually by setting
switches and plugging and
unplugging the cables.
 A ring of ten vacuum tubes
represented each digit.
 Very large machines
Vacuum Tube
First Generation Computer made of
Vacuum tubes
Second Generation: Transistors
 Transistors
 Made up of Silicon
 Silicon:
 Insulator
 It is made Semiconductor by Doping
 All the electronic devices are semiconductor devices
 And most of them are made up of transistors.
 Boolean logical gates are made of transistors.
 Combinational and sequential circuits – logic gates
 Integrated circuits – are made up of these circuits.
 Microprocessor is made up of these integrated circuits.
Moore’s Law
 Size of transistor is decreasing
 Number of transistors are increasing exponentially.
 Moore’s Law:
 Number of transistors doubles every 18 months to 2years.
 Gordon Moore: Co-founder of Intel
Moore’s Law
P4 Extreme Ed.
178 millions w/ 2MB L3
IBM POWER5 has
276 million transistors
Intel Dual-Core Xeon (P4-based Tulsa)
w/ 16MB unified L3: 1.328 billion, 2006
2,250
Core 2 Duo (Conroe)
291 millions, July 2006
42 millions
Exponential growth
Transistor count will be doubled every 18 months
 Gordon Moore, Intel co-founder
Stored Program Concept
 Von Neumann Model
 Program is first stored in the memory and each instruction is
then executed one by one by the processor.
Third Generation: Integrated Circuits
 In second generation, discrete components such as transistors
, resistors etc were manufactured separately and soldered on
the circuit board.
 This made the entire manufacturing process from transistor
to circuit board cumbersome and expensive
 Then Integrated circuits were introduced.
 SSI circuits
 LSI circuits
 VSLI circuits
 Later generations used LSI, VLSI and new technology.
Data Representation
Number System
Binary Number System
Decimal Number System
What kinds of data do we need to
represent?
 Numbers – signed, unsigned, integers, floating point,





complex, rational, irrational, …
Text – characters, strings, …
Images – pixels, colors, shapes, …
Sound - numbers
Logical – true, false
Instructions – strings of characters
How do we represent data in a
computer?
 At the lowest level, a computer is an electronic machine.
 Works by controlling the flow of electrons
 Easy to recognize two conditions:
1. Presence of a voltage – we’ll call this state “1”
2. Absence of a voltage – we’ll call this state “0”
Computer is a binary digital system
Digital system:
• Finite number of symbols
Decimal Number system:
• 10 symbols, [0,9]
Binary (base two) system:
• Has two symbols representing two stable states: 0 and 1
 Physical devices used to store and process data in computers are
two state devices like
 semiconductor switches (ON/OFF)
 Magnetic surface alignment (N-S,S-N)
 Flip-flops ( low voltage, high voltage)
Bits and bytes
 Bits – binary digits (binary: only two possible values)
 Byte – collection of bits
 1 Byte = 8 Bits
Bits, Bytes, and Words
 A bit is a single binary digit (a 1 or 0).
 A byte is 8 bits
 A word is 32 bits or 4 bytes
 Long word = 8 bytes = 64 bits
 Quad word = 16 bytes = 128 bits
 Programming languages use these standard number of bits
when organizing data storage and access.
Bits, Bytes
Unit
kilobyte
Symbol Number of Bytes
10
gigabyte
KB
MB
GB
2 = 1024
20
2 (over 1 million)
30
2 (over 1 billion)
terabyte
TB
2
megabyte
40
(over 1 trillion)
Bit Permutations
1 bit
2 bits
3 bits
0
1
00
01
10
11
000
001
010
011
100
101
110
111
4 bits
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Each additional bit doubles the number of possible permutations
Representation of Numbers

Binary Numbers
 Unsigned Integers
 Signed Magnitude
 1’s Complement
 2’s Complement
Unsigned Integers
 Weighted positional notation
 like decimal numbers: “329”
 “3” is worth 300, because of its position, while “9” is only
worth 9
most
significant
329
102
101
100
3x100 + 2x10 + 9x1 = 329
22
101
21
least
significant
20
1x4 + 0x2 + 1x1 = 5
Unsigned Integers (cont.)
 An n-bit unsigned integer represents 2n values:
from 0 to 2n-1.
22 21 2 0
0
0
0
0
0
1
0
1
0
0
1
1
1
1
0
0
0
1
0
1
2
3
4
5
1
1
1
1
0
1
6
7
Unsigned Binary Arithmetic
carry
10010
+ 1001
11011
10010
+ 1011
11101
10111
+ 111
11110
 Base-2 addition – just like base 10
 Add from right to left, propagating carry
1111
+
1
10000
Signed Integers
 With n bits, we have 2n distinct values.
 Assign about half to positive integers (1 through 2n-1)
and about half to negative (- 2n-1 through -1)
 That leaves two values: one for 0, and one extra
Representation of Signed Integers Cont…
 Ex: n = 3
Signed magnitude
000
001
010
011
100
101
110
111
+0
+1
+2
+3
-0
-1
-2
-3
 Positive integers
 Just like unsigned : zero in most significant (MS) bit
00101 = 5
 Negative integers
 Set MS bit to show negative,
other bits are the same as unsigned
10101 = -5
 Inference
 MS bit indicates sign: 0=positive, 1=negative
Question
 Given n bit string, What is the Maximum number we
can represent in Signed Magnitude form?

1
1
2n-1 2n-2
1 .
. .
.
.
.
.
.
.
.
.
1
22 21 20
The Max. value is : 2n-1 -1
The Min. value is : - 2n-1 -1
Ex: Given 5 bits,
Max. number in signed magnitude form is: 24 -1 =15
Min. number in signed magnitude form is: -24 -1= -15
1’s Complement Representation
 Positive numbers representation is same as signed




integers.
Negative numbers represented by flipping all the bits of
corresponding positive numbers
For Example:
+5 is represented as 00101
-5 is represented by 11010
Example: 1’s Complement
 Example 1:





How we represent -12 in 1’s complement form
Step1: Take +12 in binary representation
 01100
Step2: Flip all the bits of the above
 10011
Inference
 -12 representation in 1’s complement form: 10011
 +12 representation in 1’s complement form: 01100
Limitations!
 Problems with sign-magnitude and 1’s complement!
 Two representations of zero (+0 and –0)
 Arithmetic circuits are complex to implement above
representation
Two’s Complement Representation
 If number is positive or zero
 Normal binary representation
 If number is negative
 Start with positive number
 Flip every bit (i.e., take the one’s complement)
 Then add one
Example:
00101 (5)
11010 (1’s comp)
+
1
11011 (-5)
01001 (9)
10110
(1’s comp)
+
1
10111 (-9)
Advantage of 2’s complement
 Two’s complement representation is developed to make
circuits easy for arithmetic.
 For each positive number (X), assign value to its negative (-X),
such that X + (-X) = 0 with “normal” addition, ignoring carry
out
00101 (5)
+ 11011 (-5)
00000 (0)
01001 (9)
+ 10111 (-9)
00000 (0)
Example:2+(-3)
 Express -3 in 2’s complement form:
 00011
1’s Complement of 3
 11100
2’s Complement of 3  11101 i.e. -3
2

00010
-3 
11101
11111
 3





Interpret the result
 11111
 Look at MSB  1  the result is negative
 What is the decimal equivalent of the result
 Take 2’s complement of 11111
 Flip the bits to get 1’s complement 0000
 Add 1, we get 0001, hence the number is -1
2’s Complement Signed Numbers
23
0
0
0
0
0
0
0
0
22
0
0
0
0
1
1
1
1
21
0
0
1
1
0
0
1
1
20
0
1
0
1
0
1
0
1
0
1
2
3
4
5
6
7
23
1
1
1
1
1
1
1
1
22
0
0
0
0
1
1
1
1
21 20
0 0
0 1
1 0
1 1
0 0
0 1
1 0
1 1
-8
-7
-6
-5
-4
-3
-2
-1
Base conversion
•Convert a number from one number system to another
Binary to Decimal and Decimal to Binary
Decimal to Octal and Octal to Decimal
Octal to Binary and Binary to Octal
Binary to Hexadecimal and Hexadecimal to Binary
The Decimal Number System
The decimal number system is a positional
number system.
 Example:

5 6 2 1
103 102 101 100
1 X 100
2 X 101
6 X 102
5 X 103
=
1
= 20
= 600
= 5000
The Decimal Number System
The decimal number system is also known as
base 10.
 The values of the positions are calculated by
taking 10 to some power.
 Why is the base 10 for decimal numbers?


Because we use 10 digits, the digits 0 through 9.
The Binary Number System
Uses two symbols 0 and 1 to represent
numbers
 Hence base 2

The Binary Number System (con’t)
The binary number system is also a
positional numbering system.
 Example of a binary number and the values
of the positions:

1 0 0 1 1 0 1
26 25 24 23 22 21 20
Total number of unique
representations using n
bits
A sequence of n bits has 2n
possible unique
representations.
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
0000
0001
0010
0011
0100
0101
0110
0111
1000
1001
1010
1011
1100
1101
1110
1111
Converting from Binary to Decimal
1 0 0 1 1 0 1
26 25 24 23 22 21 20
20 = 1
21 = 2
22 = 4
23 = 8
24 = 16
25 = 32
26 = 64
1 X 20 = 1
0 X 21 = 0
1 X 22 = 4
1 X 23 = 8
0 X 24 = 0
0 X 25 = 0
1 X 26 = 64
7710
Converting from Binary to Decimal
Class Assignment:
Binary
Decimal
11101 (1x24 + 1x23 + 1x22 + 0x21 =16 + 8 + 4 + 0 + 1
0)
+
1x2
= 29
1010101
100111
Converting Decimal Number to Binary
Number
 Make a list of the binary place values up to the number being
converted.
 Perform successive divisions by 2, placing the remainder of 0 or 1
in each of the positions from right to left.
 Continue until the quotient is zero.
Example:
5510
25 24 23 22 21 20
32 16 8 4 2 1
1
1 0 1 1 1
Procedure for decimal to binary
conversion
2 | 55_
2 | 27
2 | 13_
2 | 6_
2 | 3_
2 | 1_
0
1 (LSB)
1
1
0
1
1 (MSB)
Converting From Decimal to Binary
Class Assignment
Decimal
82
107
Binary
(82)10=(1010010)2
(107)10=(1101011)2
-14
(-14)10=(10010)2
-329
(-329)10=(1010110111)2
HexaDecimal Number System
 Base 16
 16 distinct symbols
 0-9,A,B,C,D,E,F
 Convert binary number to hexadecimal number
 Decimal to Octal
 Divide the magnitude by 8
 Record the remainder
 Keep on dividing the quotient and record the remainders
 Write the remainders in reverse order
 Same as Decimal to Binary Conversion
 Example
 (404)10
(624)8
Octal to Decimal
 Method is same as Binary to decimal conversion
 Only the base changes to 8
 Verify previous example
 (624)8
(6 X 82) + (2 X 81) + (4 X 80)
Result is (404)10
Octal to Binary
 Method I
 Convert Octal to Decimal
 Then convert Decimal to Binary
 Method II
 Write 3-bit binary equivalent of each Octal digit in Octal
Number
 Example
 (624)8
(110010100)2
Binary to Octal
 Group bits (3-bit group) from right to left
 Convert each 3- bit group to each Octal digit
 Example
110010100
(624)8
Hexadecimal Number System
Exercise
 Convert Hexadecimal Number to Binary Number
 ADF6
 DB69
 CA36
 5678
 DABC