Transcript ppt

CDA 3100 Summer 2013
Special Thanks
• Thanks to Dr. Zhenghao Zhang for letting me
use his class slides and other materials as a
base for this course
Course Information
About Me
•
•
•
•
•
Name: Britton Dennis
Email: [email protected]
Office: LOV 105A
Office Hours: Thursday 9:30 AM – 12:30 PM
Site:
http://ww2.cs.fsu.edu/~dennis/cda3100_sum
mer_2013
4/10/2016
CDA3100
4
Class Communication
• This class will use class web site to post news,
changes, and updates. So please check the
class website regularly
• Please also make sure that you check your
emails on the account on your University
record
4/10/2016
CDA3100
5
Lecture Notes and Textbook
• All the materials that you will be tested on will be
covered in the lectures
– All lectures will be posted on the website in both
(Microsoft Office 2010 published) .pptx and in the more
universally viewable .pdf
– The textbook isn’t required, but it may be worth
purchasing for review and for further detail explanations
– In particular, the appendix will be useful for MIPS
instruction references
– The lectures will be based on the textbook and any
handouts distributed in class
4/10/2016
CDA3100
6
Required Textbook
• The required textbook for this class is
– “Computer Organization and Design”
• The hardware/software interface
– By David A. Patterson and John L. Hennessy
– Fourth Edition
4/10/2016
CDA3100
7
Grades and Weighting
• In Class Exercises – 5%
– 5-7 exercises will be given during class throughout the semester
– Only top 4 will be graded
• Homework – 40%
– 7 problems sets will be given throughout the semester
– There will be two windows to turn them in.
• Up to the first is the real deadline
• Up to the second, you will receive a 10% deduction.
• After that, the assignment won’t be accepted
– For accreditation reasons, the department requires you to pass a particular
assignment to pass the course
• Exams
–
–
–
–
4/10/2016
Midterm – 20%
Final – 35%
Cumulative
About 10 Multiple Choice and 2-3 Short Response
CDA3100
8
Motivations
What you will learn to answer
(among other things)
• How does the software instruct the hardware
to perform the needed functions
• What is going on in the processor
• How a simple processor is designed
Why This Class Important?
• If you want to create better computers
– It introduces necessary concepts, components, and
principles for a computer scientist
– By understanding the existing systems, you may
create better ones
• If you want to build software with better
performance
• If you want to have a good choice of jobs
• If you want to be a real computer scientist
4/10/2016
CDA3100
11
Required Background
Required Background
• You will probably suffer if you do not have the
required C/C++ programming background.
• In this class, we will be doing assembly coding, which
is more advanced than C/C++.
• If you do not have a clear understanding at this
moment of array and loop , it is recommended
that you take this course at a later time, after getting
more experience with C/C++ programming.
Array – What Happens?
#include <stdio.h>
int main (void)
{
int A[5] = {16, 2, 77, 40, 12071};
A[A[1]] += 1;
return 0;
}
Loop – What Happens?
#include <stdio.h>
int main ()
{
int A[5] = {16, 20, 77, 40, 12071};
int result = 0;
int i = 0;
while (result < A[i]) {
result += A[i];
i++;
}
return 0;
}
Getting Started!
Decimal Numbering System
• We humans naturally use a particular numbering system
4/10/2016
CDA3100
17
Decimal Numbering System
• For any nonnegative integer d n d n 1  d1d 0, its
value is given by
n
i
n
n 1
1
0
d

10

d

10

d

10



d

10

d

10
 i
n
n 1
1
0
i 0
 ( ((( 0  10  d n )  10  d n 1 )  10    d1 )  10  d 0
– Here d0 is the least significant digit and dn is the
most significant digit
4/10/2016
CDA3100
18
General Numbering System – Base X
• Besides 10, we can use other bases as well
– In base X,
n
d  X
i 0
i
i
 d n  X n  d n 1  X n 1    d1  X 1  d 0  X 0
 ( ((( 0  X  d n )  X  d n 1 )  X    d1 )  X  d 0
– Then, the base X representation of this number is
defined as dndn-1…d2d1d0.
– The same number can have many representations
on many bases. For 23 based 10, it is
4/10/2016
• 23ten
• 10111two
CDA3100
• 17
, often written as 0x17.
19
Commonly Used Bases
Base
Common Name
Representation
Digits
10
Decimal
5023ten or 5023
0-9
2
Binary
1001110011111two
0-1
8
Octal
11637eight
0-7
16
Hexadecimal
139Fhex or 0x139F
0-9, A-F
– Note that other bases are used as well including 12 and 60
• Which one is natural to computers?
– Why?
4/10/2016
CDA3100
20
Meaning of a Number Representation
• When we specify a number, we need also to
specify the base
– For example, 10 presents a different quantity in a
different base
4/10/2016
CDA3100
21
Question
• How many different numbers that can be
represented by 4 bits?
Question
• How many different numbers that can be
represented by 4 bits?
• Always 16 (24), because there are this number
of different combinations with 4 bits,
regardless of the type of the number these 4
bits are representing.
• Obviously, this also applies to other number of
bits. With n bits, we can represent 2n different
numbers. If the number is unsigned integer, it
is from 0 to 2n-1.
Conversion between Representations
• Now we can represent a quantity in different
number representations
– How can we convert a decimal number to binary?
– How can we then convert a binary number to a
decimal one?
4/10/2016
CDA3100
25
Conversion Between Bases
• From binary to decimal example
0
0
0
1
0
0
1
1
1
0
0
1
1
1
1
1
15
14
13
12
11
10
9
8
7
6
5
4
3
2
1
0
215 214 213 212 211 210
29
28
27
26
25
24
23
22
21
20
 212  29  28  27  24  23  22  21  20
 4096  512  256  128  16  8  4  2  1
 5023
4/10/2016
CDA3100
26
Converting from binary to decimal
• Converting from binary to decimal. This
conversion is also based on the formula:
d = dn-12n-1 + dn-22n-2 +…+ d222 + d121 + d020
while remembering that the digits in the
binary representation are the coefficients.
• For example, given 101011two, in decimal, it is
25 + 23 + 21 + 20 = 43.
Conversion Between Bases
• Converting from decimal to binary:
– Repeatedly divide it by 2, until the quotient is 0.
– Going from top to bottom, write down the
remainder from right to the left.
• Example: 11.
Quotient
Remainder
5
1
2
1
1
0
0
1
Digging a little deeper
• Why can a binary number be obtained by keeping on
dividing by 2, and why should the last remainder be
the first bit?
• Note that
– Any integer can be represented by the summation
of the powers of 2:
d = dn-12n-1 + dn-22n-2 +…+ d222 + d121 + d020
– For example, 19 = 16 + 2 + 1 = 1 * 24 + 0 * 23 + 0 *
22 + 1 * 21 + 1 * 20.
– The binary representation is the binary
coefficients. So 19ten in binary is 10011two.
Digging a little deeper
• In fact, any integer can be represented by the summation of
the powers of some base, where the base is either 10, 2 or 16
in this course. For example, 19 = 1 * 101 + 9 * 100. How do you
get the 1 and 9? You divide 19 by 10 repeatedly until the
quotient is 0, same as binary!
• In fact, the dividing process is just an efficient way to get the
coefficients.
• How do you determine whether the last bit is 0 or 1? You can
do it by checking whether the number is even or odd. Once
this is determined, you go ahead to determine the next bit, by
checking (d - d020)/2 is even or odd, and so on, until you don’t
have to check any more (when the number is 0).
Conversion between Base 16 and
Base 2
• Extremely easy.
– From base 2 to base 16: divide the digits in to
groups of 4, then apply the table.
– From base 16 to base 2: replace every digit by a 4bit string according to the table.
• Because 16 is 2 to the power of 4.
Addition in binary
• 39ten + 57ten = ?
• How to do it in binary?
Addition in Binary
• First, convert the numbers to binary forms.
We are using 8 bits.
– 39ten -> 001001112
– 57ten -> 001110012
• Second, add them.
00100111
00111001
01100000
Addition in binary
• The addition is bit by bit.
• We will encounter at most 4 cases, where the
leading bit of the result is the carry:
1.
2.
3.
4.
0+0+0=00
1+0+0=01
1+1+0=10
1+1+1=11
Subtraction in Binary
• 57ten – 39ten = ?
Subtraction in Binary
00111001
00100111
00010010
Subtraction in binary
• Do this digit by digit.
• No problem if
– 0 - 0 = 0,
– 1-0=1
– 1 – 1 = 0.
• When encounter 0 - 1, set the result to be 1 first, then borrow 1 from the
next more significant bit, just as in decimal.
– Borrow means setting the borrowed bit to be 0 and the bits from the bit following the
borrowed bit to the bit before the current bit to be 1.
– Think about, for example, subtracting 349 from 5003 (both based 10). The last digit is
first set to be 4, and you will be basically subtracting 34 from 499 from now on.