CS 2204 Fall 2005 - NYU Polytechnic School of Engineering
Download
Report
Transcript CS 2204 Fall 2005 - NYU Polytechnic School of Engineering
CS 2204
Lab 10
Digital Logic
and
State Machine Design
Appendices
Labs 9, 10, 11, 12, 13
Experiment 6
?
Spring 2014
Appendices Labs 10 - 13 Outline
Lab 10
Presentation
Machine Player Example 2 (Lab 10)
Digital product development overview (Lab 11)
Component selection for a new chip
• Xilinx component usage
Component selection for a new PCB
• TTL LS SSI chip usage
Semiconductor technology overview (Lab 12)
Submitting the term project
Submitting the term project (Lab 13)
Individual work
Developing Ppm Block 6
CS 2204 Spring 2014 Experiment 6 Appendices
Page 2
Block 6, Machine Play Block Development
Example 1
1.
Lab 10
Start with the black box view where the outputs are fixed and the
input/output relationship
a)
b)
c)
?
Understand the game rules and how the machine player has to interact
with the rest of the Ppm digital system
Determine the playing strategy (intelligence)
Determine the inputs
We know the game rules already !
Block 6
?
Play on the
(rightmost)
largest regular
reward position
(directly if
equal)
(Action 0)
CS 2204 Spring 2014 Experiment 6 Appendices
Page 3
Block 6, Machine Play Block Development
Example 1
1.
Lab 10
Start with the black box view where the outputs
are fixed and the input/output relationship
b)
Play on the
(rightmost)
largest
regular
reward
position
(directly if
equal)
(Action 0)
Determine the playing strategy (intelligence)
Always plays (does not skip at all)
Plays on the largest regular reward points position directly or
with an addition (choose direct playing if reward points are
equal)
If two or more positions have the same regular reward,
selects the rightmost one (can also select randomly, or round
robin, etc.)
If playing directly on a left side position gives the same
regular reward points as playing with an addition on the right
side, playing directly on the left side is chosen
CS 2204 Spring 2014 Experiment 6 Appendices
Page 4
Block 6, Machine Play Block Development
Example 1
1.
Lab 10
Start with the black box view where the outputs
are fixed and the input/output relationship
c)
Determine the inputs
Play on the
(rightmost)
largest
regular
reward
position
(directly if
equal)
(Action 0)
We have to collect eight regular reward points for eight
possibilities
•
•
We will collect the eight regular reward points sequentially
•
Four regular reward points on four displays with direct playing
Four regular reward points on four displays with additions
This will take 8 clock periods !
Then, we will play on a position in the ninth clock period
Player 2 spends
NINE P2clk
periods to think
CS 2204 Spring 2014 Experiment 6 Appendices
Page 5
Block 6, Machine Play Block Development
1.
Example 1
Lab 10
Start with the black box view where the outputs are fixed
and the input/output relationship
a)
b)
c)
Understand the game rules and how the machine player has to
interact with the rest of the Ppm digital system
Determine the playing strategy (intelligence)
Determine the inputs
Play on the
We need to collect the regular reward
points : RWD
We will collect eight regular
reward points sequentially
We have to input : P2sturn,
Clearp2ffs, P2clk
?
(rightmost)
largest regular
reward position
(directly if
equal)
(Action 0)
Block 6
?
CS 2204 Spring 2014 Experiment 6 Appendices
Page 6
Block 6, Machine Play Block Development
1.
Example 1
Lab 10
Start with the black box view where the outputs are fixed
and the input/output relationship
a)
b)
c)
Understand the game rules and how the machine player has to
interact with the rest of the Ppm digital system
Determine the playing strategy (intelligence)
Determine the inputs
We input RWD
RWD
We input P2sturn,
Clearp2ffs, P2clk
Play on the
(rightmost) largest
regular reward
position (directly
if equal)
(Action 0)
P2sturn
8
Block 6
?
Clearp2ffs
P2clk
CS 2204 Spring 2014 Experiment 6 Appendices
Page 7
Block 6, Machine Play Block Development
1.
Example 1
Lab 10
Start with the black box view where the outputs are fixed
and the input/output relationship
a)
b)
c)
Play on the
(rightmost)
largest
regular
reward
position
(directly if
equal)
(Action 0)
Understand the game rules and how the machine player has to
interact with the rest of the Ppm digital system
Determine the playing strategy (intelligence)
Determine the inputs
The outputs are fixed !
RWD
P2sturn
4
8
P2add
Block 6
P2played
Clearp2ffs
P2clk
P2SEL
P2skip
8
P2CODE
We must connect 8 zeros to the P2CODE
lines to avoid unnecessary warnings
CS 2204 Spring 2014 Experiment 6 Appendices
Page 8
Block 6, Machine Play Block Development
Start with the black box view where the outputs are fixed and the
input/output relationship
Example 1
1.
Lab 10
•Must generate the seven outputs for correct operation
•The Ppm will stay in state 4 when the machine thinks : both P2played and P2skip are zero
•It stays in state 4 at least one Sysclk period
•The selection of inputs depends on the strategy and the implementation
CS 2204 Spring 2014 Experiment 6 Appendices
Page 9
Example 1
Block 6, Machine Play Block Development
Lab 10
2. Get the black box view with the inputs determined
and convert the textual input/output relationship
(including the playing strategy) to an operation
diagram
Convert the playing strategy to major operations
The goal is to develop an intelligent machine player
It gathers information about the current situation
Decides how to play
Partition Block 6 into subblocks
There are at least two major operations: gather reward
information and decide which position to play
Therefore, Block 6 must have at least two subblocks
•
Information Gathering Subblock
•
Decision Making Subblock
The information gathering subblock obtains the regular reward points with
additions on the four positions and determines the largest regular reward
position
The decision making subblock plays on the largest regular reward position
CS 2204 Spring 2014 Experiment 6 Appendices
Page 10
Example 1
Block 6, Machine Play Block Development
Lab 10
2. Get the black box view with the inputs determined
and convert the textual input/output relationship
(including the playing strategy) to an operation
diagram
Partition Block 6 into subblocks
Do we need another major operation ?
The information gathering subblock has to obtain the regular
reward points with addition
How can we gather and compare the four regular reward points
and then decide ?
► Sequentially !
A sequencing circuit is needed to get the regular reward points
for each position one by one !
► A new subblock is needed as the mini sequencer
CS 2204 Spring 2014 Experiment 6 Appendices
Page 11
Example 1
Block 6, Machine Play Block Development
Lab 10
2. Get the black box view with the inputs determined
and convert the textual input/output relationship
(including the playing strategy) to an operation
diagram
Partition Block 6 into subblocks
The information gathering is done in several steps
The machine player goes through steps taking several
clock periods
•
•
Another major operation, controlling major operation is
needed
A new subblock, a Sequencing Subblock is needed
Operation diagram is needed to describe what happens
in each step
•
The operation diagram and the controller imply that the Block 6
is a tiny digital system itself
CS 2204 Spring 2014 Experiment 6 Appendices
Page 12
Example 1
Block 6, Machine Play Block Development
Lab 10
2. Get the black box view with the inputs determined and convert
the textual input/output relationship (including the playing
strategy) to an operation diagram
We have sequential gather and sequential compare
A sequencing circuit is needed to get reward points, compare with the
previous largest reward and update the reward
The machine player takes several clock periods to make a decision
An operation diagram is needed
•
•
•
Convert the game rules and playing strategy to major operations
Partition Block 6 into subblocks
Block 6 is a tiny digital system itself
To get the operation diagram, check the playing strategy and
determine what to do when :
All actions happen in the last state
Some actions indicate which data to collect
All conditions indicate what to collect
CS 2204 Spring 2014 Experiment 6 Appendices
Page 13
Example 1
Block 6, Machine Play Block Development
Lab 10
2. Get the black box view with the inputs determined
and convert the textual input/output relationship
(including the playing strategy) to an operation
diagram
Adjacency
How can we gather and compare the four regular reward
points and then decide sequentially ?
The information gathering subblock has to obtain the regular
reward points with direct playing and additions
•
Regular Reward
Calculation
This is already done in Block 5 !
► Block 5 has the Regular Reward Calculation Subblock which uses
the Adjacency Subblock !
► Block 5 receives the digit played and the position tested from
Block 4
NOT
DO
IMPLEMENT THIS
INFORMATION GATHERING
CIRCUITRY COMBINATIONALLY
CS 2204 Spring 2014 Experiment 6 Appendices
Page 14
Example 1
Block 6, Machine Play Block Development
Lab 10
2. Get the black box view with the inputs determined and convert
the textual input/output relationship (including the playing
strategy) to an operation diagram
There is only one action and no condition
The action indicates we have to
Play on the
(rightmost)
largest
regular
reward
position
(directly if
equal)
(Action 0)
Collect regular reward points
•
Play on the largest regular reward position
•
Since the information gathering subblock determines which position has
the largest regular reward, decision making subblock is simple !
We can use Block 5 to get the regular reward points for each display
When the random digit is played with direct playing and addition on the
four displays
Determine which display has the largest regular reward points
We indicate which position we are testing (collecting the regular reward
points of) with direct playing and addition one by one and Block 5
determines the regular reward points for the position tested
Collecting eight regular reward points and comparing them takes eight
clock periods
Then, in the next clock period, the ninth one, we decide where to play
This strategy requires nine clock periods to play !
CS 2204 Spring 2014 Experiment 6 Appendices
Page 15
Example 1
Block 6, Machine Play Block Development
Lab 10
2. Get the black box view with the inputs determined and convert
the textual input/output relationship (including the playing
strategy) to an operation diagram
In summary, we have
Eight clock periods of regular reward collection and comparison
•
Play on the
(rightmost)
largest
regular
reward
position
(directly )
(Action 0)
By using the output of Block 5 : RWD
One clock period of decision making
How do we handle the secondary strategy ?
If two or more displays have the same largest regular reward points,
we play on the rightmost of these
If playing directly and with an addition give the same regular reward
points, we play directly
If playing directly on a left side position gives the same regular
reward points as playing with an addition on the right side, playing
directly on the left side is chosen
Do we need separate hardware for this ?
•
NO as we will see on the next slide !
CS 2204 Spring 2014 Experiment 6 Appendices
Page 16
Example 1
Block 6, Machine Play Block Development
Lab 10
2. Get the black box view with the inputs determined and convert
the textual input/output relationship (including the playing
strategy) to an operation diagram
How do we convert the strategy to an operation diagram ?
Play on the
(rightmost)
largest
regular
reward
position
(directly )
(Action 0)
Write down the steps to play
1.
2.
Get the regular reward points for position 0 with a direct play
Get the regular reward points for position 1 with a direct play and compare
with position 0
► If position 1 has a larger regular reward than position 0, keep it !
3.
Get the regular reward points for position 2 a direct play
4.
Get the regular reward points for position 3 with a direct play
5.
► If position 2 has a larger regular reward than the previous two positions, keep it !
► If position 3 has a larger regular reward than the previous three positions, keep it !
Get the regular reward points for position 0 with an addition
► If position 0 has a larger regular reward than the previous four cases,
keep it !
NOT
DO
IMPLEMENT THIS INFORMATION
GATHERING CIRCUITRY COMBINATIONALLY
CS 2204 Spring 2014 Experiment 6 Appendices
Page 17
Example 1
Block 6, Machine Play Block Development
Lab 10
2. Get the black box view with the inputs determined and convert
the textual input/output relationship (including the playing
strategy) to an operation diagram
How do we convert the strategy to an operation diagram ?
Write down the steps to play
6.
Play on the
(rightmost)
largest
regular
reward
position
(directly )
(Action 0)
Get the regular reward points for position 1 with an addition and compare
with position 0
► If position 1 has a larger regular reward than previous five points, keep it !
7.
Get the regular reward points for position 2 with an addition
8.
Get the regular reward points for position 3 with an addition
9.
Play on the position that has the largest regular reward with an addition
•
•
From right to left and
Keeping a position only if its regular reward is greater than those to the
right
Selecting direct playing if it has the same points as playing with an addition
► If position 2 has a larger regular reward than the previous six points, keep it !
► If position 3 has a larger regular reward than the previous seven points, keep it !
Implementing the secondary strategy is done by checking positions
•
NOT
DO
IMPLEMENT THIS INFORMATION
GATHERING CIRCUITRY COMBINATIONALLY
CS 2204 Spring 2014 Experiment 6 Appendices
Page 18
Block 6, Machine Play Block Development
Convert the textual input/output relationship (including the playing strategy) to an operation diagram
P2st0
P2st1
Determine position 2 regular reward with direct playing, keep it if it is larger
& record the position number
IG
Determine position 3 regular reward with direct playing, keep it if it is larger
& record the position number
IG
Determine position 0 regular reward with an addition, keep it if it is larger &
record the position number
IG
Determine position 1 regular reward with an addition, keep it if it is larger &
record the position number
IG
Determine position 2 regular reward with an addition, keep it if it is larger &
record the position number
IG
Determine position 3 regular reward with an addition, keep it if it is larger &
record the position number
IG
P2SEL
Machine
P2add
P2sturn
IG
P2st2
Clearp2ffs
Determine position 1 regular reward with direct playing, keep it if it is larger
& record the position number
P2st3
8
IG
P2st4
4
RWD
Determine position 0 regular reward with direct playing & record the position
number
P2st5
Example 1
Sequential gather and Sequential compare
An operation diagram is needed
4
P2st6
2.
Lab 10
P2sturn = 1 in S4
P2st7
Player
P2played
P2skip
Player 2 spends
NINE P2clk
periods to think
P2st8
P2clk
Based on the stored information select the position to play
D
Player 2 plays on a position
CS 2204 Spring 2014 Experiment 6 Appendices
Page 19
Block 6, Machine Play Block Development
Lab 10
Example 1
3. Convert the operation diagram to a high-level state diagram with
microoperations with the same number of states
How do we get the regular reward points without actually playing ?
How do we test each position without actually playing ?
1.
Get the regular reward points for position 0 with a direct play
2.
Get the regular reward points for position 1 with a direct play and
compare with position 0
•
•
•
•
Indicate to Block 4 and Block 5 that position 0 is tested with a direct play
P2SEL = 0001 ; P2add = 0 ; P2played = 0 ; P2skip = 0
Store RWD on register LRGRWD & store the position on register POS
LRGRWD RWD ; POS 00001
•
•
•
Indicate to Block 4 and Block 5 that position 1 is tested with a direct play
P2SEL = 0010 ; P2add = 0 ; P2played = 0 ; P2skip = 0
If RWD is greater than LRGRWD, then store RWD on LRGRWD & store the
position on POS
If RWD > LRGRWD then LRGRWD RWD ; POS 00010
•
Player 2 spends
NINE P2clk
periods to think
CS 2204 Spring 2014 Experiment 6 Appendices
Page 20
Block 6, Machine Play Block Development
Lab 10
Example 1
3. Convert the operation diagram to a high-level state diagram with
microoperations with the same number of states
How do we get the regular reward points without actually playing ?
How do we test each position without actually playing ?
3.
Get the regular reward points for position 2 with a direct play
4.
Get the regular reward points for position 3 with a direct play and
compare with position 0
•
•
•
•
Indicate to Block 4 and Block 5 that position 2 is tested with a direct play
P2SEL = 0100 ; P2add = 0 ; P2played = 0 ; P2skip = 0
Store RWD on register LRGRWD & store the position on register POS
LRGRWD RWD ; POS 00100
•
•
•
Indicate to Block 4 and Block 5 that position 3 is tested with a direct play
P2SEL = 1000 ; P2add = 0 ; P2played = 0 ; P2skip = 0
If RWD is greater than LRGRWD, then store RWD on LRGRWD & store the
position on POS
If RWD > LRGRWD then LRGRWD RWD ; POS 01000
•
Player 2 spends
NINE P2clk
periods to think
CS 2204 Spring 2014 Experiment 6 Appendices
Page 21
Lab 10
Block 6, Machine Play Block Development
Example 1
3. Convert the operation diagram to a high-level state diagram with
microoperations with the same number of states
How do we get the regular reward points without actually playing ?
How do we test each position without actually playing ?
5.
Get the regular reward points for position 0 with with an addition
6.
Get the regular reward points for position 1 with an addition and
compare with position 0
•
•
•
•
Indicate to Block 4 and Block 5 that position 0 is tested with an addition
P2SEL = 0001 ; P2add = 1 ; P2played = 0 ; P2skip = 0
Store RWD on register LRGRWD & store the position on register POS
LRGRWD RWD ; POS 10001
•
•
•
Indicate to Block 4 and Block 5 that position 1 is tested with an addition
P2SEL = 0010 ; P2add = 1 ; P2played = 0 ; P2skip = 0
If RWD is greater than LRGRWD, then store RWD on LRGRWD & store the
position on POS
If RWD > LRGRWD then LRGRWD RWD ; POS 10010
•
Player 2 spends
NINE P2clk
periods to think
CS 2204 Spring 2014 Experiment 6 Appendices
Page 22
Block 6, Machine Play Block Development
Lab 10
Example 1
3. Convert the operation diagram to a high-level state diagram with
microoperations with the same number of states
How do we get the regular reward points without actually playing ?
How do we test each position without actually playing ?
7.
Get the regular reward points for position 2 with a direct play
8.
Get the regular reward points for position 3 with a direct play and
compare with position 0
•
•
•
•
Indicate to Block 4 and Block 5 that position 2 is tested with an addition
P2SEL = 0100 ; P2add = 1 ; P2played = 0 ; P2skip = 0
Store RWD on register LRGRWD & store the position on register POS
LRGRWD RWD ; POS 10100
•
•
•
Indicate to Block 4 and Block 5 that position 3 is tested with an addition
P2SEL = 1000 ; P2add = 1 ; P2played = 0 ; P2skip = 0
If RWD is greater than LRGRWD, then store RWD on LRGRWD & store the
position on POS
If RWD > LRGRWD then LRGRWD RWD ; POS 11000
•
Player 2 spends
NINE P2clk
periods to think
CS 2204 Spring 2014 Experiment 6 Appendices
Page 23
RTL Notation used
Block 6, Machine Play Block Development
3.
Lab 10
Convert the operation diagram to a high-level state diagram with microoperations with the same number
of states
Player
P2add
P2played
P2clk
P2skip
Player 2 spends
NINE P2clk
periods to think
P2st0
P2st1
P2st2
P2st3
P2sturn
Machine
P2SEL = 1000 ; P2played = 0 ; P2skip = 0 ; P2add = 0 ;
If RWD > LRGRWD then LRGRWD RWD ; POS 01000
P2st4
Clearp2ffs
P2SEL
P2SEL = 0100 ; P2played = 0 ; P2skip = 0 ; P2add = 0 ;
If RWD > LRGRWD then LRGRWD RWD ; POS 00100
P2SEL = 0001 ; P2played = 0 ; P2skip = 0 ; P2add = 1 ;
If RWD > LRGRWD then LRGRWD RWD ; POS 10001
P2st5
8
P2SEL = 0010 ; P2played = 0 ; P2skip = 0 ; P2add = 0 ;
If RWD > LRGRWD then LRGRWD RWD ; POS 00010
P2SEL = 0010 ; P2played = 0 ; P2skip = 0 ; P2add = 1 ;
If RWD > LRGRWD then LRGRWD RWD ; POS 10010
P2st6
4
RWD
P2SEL = 0001 ; P2played = 0 ; P2skip = 0 ; P2add = 0 ;
LRGRWD RWD ; POS 00001
P2SEL = 0100 ; P2played = 0 ; P2skip = 0 ; P2add = 1 ;
If RWD > LRGRWD then LRGRWD RWD ; POS 10100
P2st7
Sequential gather and Sequential compare
A diagram with finite number of states
P2SEL = 1000 ; P2played = 0 ; P2skip = 0 ; P2add = 1 ;
If RWD > LRGRWD then LRGRWD RWD ; POS 11000
P2st8
Example 1
4
P2SEL = POS[3:0] ; P2add = POS[4] ; P2played =1 ; P2skip = 0
Player 2 plays on a position
CS 2204 Spring 2014 Experiment 6 Appendices
Page 24
Lab 10
Block 6, Machine Play Block Development
3.
Convert the operation diagram to a high-level state diagram with microoperations with the same number
of states
Register ← Source
Example 1
Sequential gather and Sequential compare
A diagram with finite number of states
RTL Notation
4
RWD
8
Clearp2ffs
Wire/bus = Source
P2SEL
Machine
P2add
P2sturn
Player
P2played
P2clk
P2skip
Player 2 spends
NINE P2clk
periods to think
CS 2204 Spring 2014 Experiment 6 Appendices
Page 25
Lab 10
Block 6, Machine Play Block Development
3.
Convert the operation diagram to a high-level state diagram with microoperations with the same number
of states
BRWD
Block 4
Test position 0
NSD
Regular reward
points of
Position 0
Block 5
Example 1
P2SEL = 0001
RWD
CS 2204 Spring 2014 Experiment 6 Appendices
Page 26
Block 6, Machine Play Block Development
Lab 10
Example 1
3. Convert the operation diagram to a high-level state diagram with
microoperations with the same number of states
Sequential gather and Sequential compare
A diagram with finite number of states
How can we generate position
selection and direct/add signals ?
The control unit generates four Test
signals one for each position and a
direct/add signal : Test3, Test2, Test1
and Test0 and Testadd
Test0 is 1 if position 0 is tested : 0001
Test1 is 1 if position 1 is tested : 0010
Test2 is 1 if position 2 is tested : 0100
Test3 is 1 if position 3 is tested : 1000
Testadd is 0 the first four clock periods
Testadd is 1 the next four clock periods
CS 2204 Spring 2014 Experiment 6 Appendices
Page 27
Lab 10
Block 6, Machine Play Block Development
4. From the high-level state diagram, obtain the datapath
•
•
•
•
Sequential gather and Sequential compare
Continue to partition the datapath into subblocks
Design each (sub)block
Implement microperations in datapath hardware
A
RWD 8
A>B
8-bit
Comparator
Gt
8
Information
Gathering
RWD 8
D
CE
Store
Datapath
LRGRWD
8-bit
Register
C
P2clk
CLR
Q
8
LRGRWD
LRGRWD
B
Test0
D0
Test1
D1
Test2
D2
Test3
D3
TestAdd
Clr
Store
POS
5-bit
Register
D4
Q0
POS0
Q1
POS1
Q2
POS2
Q3
POS3
Q4
P2A
CE
C
P2clk
CLR
Clr
CS 2204 Spring 2014 Experiment 6 Appendices
P2skip
Page 28
Lab 10
Block 6, Machine Play Block Development
Example 1
4. From the high-level state diagram, obtain the datapath
•
•
•
•
Sequential gather and Sequential compare
Continue to partition the datapath into subblocks
Design each (sub)block
Implement microperations in datapath hardware
Datapath
POS0
Decision Making
Test0
P2SEL0
POS1
Test1
POS2
POS3
Test2
P2SEL1
P2SEL2
Play
Test3
P2SEL3
P2A
TestAdd
In Information Gathering
Play
P2add
P2played
0
CS 2204 Spring 2014 Experiment 6 Appendices
P2skip
Page 29
5.
From the high-level state diagram and the datapath, obtain the low-level state diagram
Player 2 plays on a position
P2st1
P2st2
P2st3
Test0 = 1 ; TestAdd = 1 ;
If Gt == 1 then Store = 1
Test1 = 1 ; TestAdd = 1 ;
If Gt == 1 then Store = 1
Test2 = 1 ; TestAdd = 1 ;
If Gt == 1 then Store = 1
Test3 = 1 ; TestAdd = 1 ;
If Gt == 1 then Store = 1
P2st8
P2SEL = POS ; P2add = POS[4] ; P2played =1 ; P2skip = 0
Test3 = 1 ; TestAdd = 0 ;
If Gt == 1 then Store = 1
P2st4
P2SEL = 1000 ; P2played = 0 ; P2skip = 0 ; P2add = 1 ;
If RWD > LRGRWD then LRGRWD RWD ; POS 11000
Test2 = 1 ; TestAdd = 0 ;
If Gt == 1 then Store = 1
P2st5
P2SEL = 0100 ; P2played = 0 ; P2skip = 0 ; P2add = 1 ;
If RWD > LRGRWD then LRGRWD RWD ; POS
10100
Test1 = 1 ; TestAdd = 0 ;
If Gt == 1 then Store = 1
P2st6
P2SEL = 0010 ; P2played = 0 ; P2skip = 0 ; P2add = 1 ;
If RWD > LRGRWD then LRGRWD RWD ; POS
10010
Test0 = 1; TestAdd = 0 ; Store = 1
P2st7
P2st0
P2st1
P2st2
P2st3
P2st4
P2SEL = 0001 ; P2played = 0 ; P2skip = 0 ; P2add = 1 ;
If RWD > LRGRWD then LRGRWD RWD ; POS 1
0001
P2st8
P2SEL = 1000 ; P2played = 0 ; P2skip = 0 ; P2add = 0 ;
If RWD > LRGRWD then LRGRWD RWD ; POS 01000
P2st5
P2SEL = 0100 ; P2played = 0 ; P2skip = 0 ; P2add = 0 ;
If RWD > LRGRWD then LRGRWD RWD ; POS
00100
P2st6
P2SEL = 0010 ; P2played = 0 ; P2skip = 0 ; P2add = 0 ;
If RWD > LRGRWD then LRGRWD RWD ; POS
00010
P2st7
P2SEL = 0001 ; P2played = 0 ; P2skip = 0 ; P2add = 0 ;
LRGRWD RWD ; POS 00001
P2st0
4
4
Example 1
Lab 10
Block 6, Machine Play Block Development
Play = 1
Player 2 plays on a position
CS 2204 Spring 2014 Experiment 6 Appendices
Page 30
Eight control signals
Block 6, Machine Play Block Development
6.
Decide about how to implement the control unit (sequencer)
Sequential gather and Sequential compare
Example 1
One status signal
Hardwiring or microprogramming ?
•
RWD
Lab 10
Hardwiring is acceptable if it is not a complex digital system : It is the case with the Ppm term project
4
Datapath
8
P2SEL
P2add
Gather reward points & compare them
Select one ≡ Make a decision
P2clk
P2played
P2skip
Gt
Play
Store
Clr
Test3
Test2
Test1 Test0
TestAdd
P2clk
Clearp2ffs
P2sturn
Control Unit
• Always plays on a position : It does not skip
• Plays on the position with the largest regular reward by trying directly or with an addition
• If two or more positions have the same reward, plays on the rightmost position
CS 2204 Spring 2014 Experiment 6 Appendices
Page 31
Hardwiring or microprogramming ?
Hardwiring is acceptable if it is not a complex digital system : It is the case
with the Ppm term project
•
Example 1
Block 6, Machine Play Block Development
Sequential gather and Sequential compare
4
P2st8
Player 2 plays on a position
Play = 1
Test3 = 1 ; TestAdd = 1 ;
If Gt == 1 then Store = 1
Test2 = 1 ; TestAdd = 1 ;
If Gt == 1 then Store = 1
Test1 = 1 ; TestAdd = 1 ;
If Gt == 1 then Store = 1
Test0 = 1 ; TestAdd = 1 ;
If Gt == 1 then Store = 1
Test3 = 1 ; TestAdd = 0 ;
If Gt == 1 then Store = 1
Test2 = 1 ; TestAdd = 0 ;
If Gt == 1 then Store = 1
Test1 = 1 ; TestAdd = 0 ;
If Gt == 1 then Store = 1
Test0 = 1; TestAdd = 0 ; Store = 1
P2st1
P2st2
P2st3
P2st4
P2st5
P2st6
P2st7
Lab 10
6. Decide about how to implement the control unit (sequencer)
P2st0
Page 32
CS 2204 Spring 2014 Experiment 6 Appendices
7.
Implement the sequencer which is treated as a state machine
Example 1
Lab 10
Block 6, Machine Play Block Development
Sequential gather and Sequential compare
Design the hardwired sequencer
How do we implement the round
robin trace of the states ?
0–1–2–3–4–5–6–7–8
0–1–2–3–4–5–6–7–8
…
We need a counter (not a register)
to keep track of the states
A counter + decoder combination is
needed to keep track of the states
We need a combination of
► 4-bit Up counter
► 3-to-8 Decoder
To keep track of the current state
CS 2204 Spring 2014 Experiment 6 Appendices
Page 33
7.
Implement the sequencer which is treated as a state machine
Example 1
Lab 10
Block 6, Machine Play Block Development
Sequential gather and Sequential compare
Design the hardwired sequencer
How do we know when we have to count up ?
0–1–2–3–4–5–6–7–8
We start counting when it is PPm state 4 (P2sturn =1)
How do we stop counting when we reach state 8 ?
0–1–2–3–4–5–6–7–8
When we reach state 8, P2s8 is 1 since we play
in state 8
We count up (enable counting) if we are
in Ppm state 4 and P2s8 is 0
Counter enable input = P2sturn P2s8
CS 2204 Spring 2014 Experiment 6 Appendices
Page 34
Block 6, Machine Play Block Development
Implement the sequencer which is treated as a state machine
Counter enable input = P2sturn P2s8
A counter + decoder combination is
needed to keep track of the states
Example 1
Sequential gather and Sequential compare
Design the hardwired sequencer
P2sturn
4-bit up counter
CE
P2s8
P2streg0
Q1
P2streg1
Q2
P2streg2
A1
A2
P2streg3
E1
P2sturn
Clearp2ffs
A0
Q3
C
P2clk
Q0
3-to-8 Decoder
7.
P2streg
Lab 10
D0
P2s0
D1
P2s1
D2
P2s2
D3
P2s3
D4
P2s4
D5
P2s5
D6
P2s6
D7
P2s7
E0
CLR
P2s8
When it is state 8, P2s8 is 1
Counter enable input = P2sturn P2s8
CS 2204 Spring 2014 Experiment 6 Appendices
Page 35
Block 6, Machine Play Block Development
Implement the sequencer which is treated as a state machine
Counter enable input = P2sturn P2s8
A counter + decoder combination is
needed to keep track of the states
Example 1
Sequential gather and Sequential compare
Design the hardwired sequencer
P2sturn
4-bit up counter
CE
P2s8
P2streg0
Q1
P2streg1
Q2
P2streg2
A1
A2
P2streg3
E1
P2sturn
Clearp2ffs
A0
Q3
C
P2clk
Q0
3-to-8 Decoder
7.
P2streg
Lab 10
D0
P2s0
D1
P2s1
D2
P2s2
D3
P2s3
D4
P2s4
D5
P2s5
D6
P2s6
D7
P2s7
E0
CLR
P2s8
Clearp2ffs is 1 after Player 2 plays
CS 2204 Spring 2014 Experiment 6 Appendices
Page 36
7.
Implement the sequencer which is treated as a state machine
Example 1
Lab 10
Block 6, Machine Play Block Development
Sequential gather and Sequential compare
Design the hardwired sequencer
Obtain Expressions
Obtain gate networks for the control signals
Test0 is 1 when it is
state 0 or state 4
Test0 = P2s0 + P2s4
Test1 is 1 when it is
state 1 or state 5
Test1 = P2s1 + P2s5
Test2 is 1 when it is
state 2 or state 6
Test2 = P2s2 + P2s6
Test3 is1 when it is
state 3 or state 7
Test3 = P2s3 + P2s7
Play is 1 when it
is state 8
Play = P2s8
CS 2204 Spring 2014 Experiment 6 Appendices
Page 37
7.
Implement the sequencer which is treated as a state machine
Example 1
Lab 10
Block 6, Machine Play Block Development
Sequential gather and Sequential compare
Design the hardwired sequencer
Obtain Expressions
Obtain gate networks for the control signals
Store is 1 when it is
•
•
•
•
•
•
•
•
State 0 or
State 1 and Gt is 1 or
State 2 and Gt is 1 or
State 3 and Gt is 1 or
State 4 and Gt is 1 or
State 5 and Gt is 1 or
State 6 and Gt is 1 or
State 7 and Gt is 1
Store is 1 when it is
• Not state 8 and
• It is either state 0 or
• Gt is 1
Store = P2s8 (P2s0 + Gt)
CS 2204 Spring 2014 Experiment 6 Appendices
Page 38
Implement the sequencer which is treated as a state machine
Sequential gather and Sequential compare
Design the hardwired sequencer
P2sturn
4-bit up counter
CE
P2s8
P2streg0
Q1
P2streg1
Q2
P2streg2
Store is 1 when it is not state 8
and it is either state 0 or Gt is 1
A1
A2
P2streg3
E1
P2sturn
Clearp2ffs
A0
Q3
C
P2clk
Q0
CLR
E0
3-to-8 Decoder
7.
Example 1
Lab 10
Block 6, Machine Play Block Development
P2streg
D0
P2s0
D1
P2s1
D2
P2s2
D3
P2s3
D4
P2s4
D5
P2s5
D6
P2s6
D7
P2s7
P2s8
Store = P2s8 (P2s0 + Gt)
CS 2204 Spring 2014 Experiment 6 Appendices
Page 39
Lab 10
Block 6, Machine Play Block Development
7.
Implement the sequencer which is treated as a state machine
Example 1
Sequential gather and Sequential compare
Design the hardwired sequencer
TestAdd is 1 when it is state
4 or 5 or 6 or state 7
TestAdd = P2s4 + P2s5 + P2s6 + P2s7
TestAdd = P2streg2
CS 2204 Spring 2014 Experiment 6 Appendices
Page 40
Lab 10
Block 6, Machine Play Block Development
7.
Implement the sequencer which is treated as a state machine
Example 1
Sequential gather and Sequential compare
Design the hardwired sequencer
Clr is 1 when Clearp2ffs is 1
Clr = Clearp2ffs
Clearp2ffs is 1 after Player 2 plays
CS 2204 Spring 2014 Experiment 6 Appendices
Page 41
Lab 10
Block 6, Machine Play Block Development
7. Implement the sequencer which is treated as a state machine
Sequential gather and Sequential compare
Design the hardwired sequencer
Example 1
Test0
4-bit up counter
CE
P2s8
P2streg0
Q1
P2streg1
Q2
P2streg2
P2streg
P2streg3
E1
P2sturn
Clearp2ffs
Store
P2s0
A1
A2
Clr
D0
A0
Q3
C
P2clk
Q0
3-to-8 Decoder
P2sturn
Test1 Test2 Test3 TestAdd Play
D1
P2s1
D2
P2s2
D3
P2s3
D4
P2s4
D5
P2s5
D6
P2s6
D7
P2s7
E0
CLR
Clearp2ffs
P2s8
P2s8
P2s8
P2s0
Gt
P2streg2
Use this counter+decoder circuit if your machine
player does not skip and has nine states
Control Unit
CS 2204 Spring 2014 Experiment 6 Appendices
Page 42
Start implementing the circuits of Block 6 on computer
•
Sequential gather and Sequential compare
Example 1
Lab 10
Block 6, Machine Play Block Development
Final digital system design on paper
Datapath
Control Unit
CS 2204 Spring 2014 Experiment 6 Appendices
Page 43
Block 6, Machine Play Block Development
Lab 10
Start implementing the circuits of Block 6 on computer
Example 1
• Sequential gather and Sequential compare
Copy the termproject folder and paste it as exp6
Start drawing the schematics by using the design on paper
Perform simulations
CS 2204 Spring 2014 Experiment 6 Appendices
Page 44
Lab 10
Block 6, Machine Play Block Development
1.
Start with the black box view where the outputs are fixed and the
input/output relationship
Example 2
a)
b)
c)
Understand the game rules and how the machine player has to interact
with the rest of the Ppm digital system
Determine the playing strategy (intelligence)
Determine the inputs
There is an adjacency ?
N
?
Block 6
?
Play on the
(rightmost)
largest regular
reward position
(directly if
equal)
(Action 0)
Y
Play on the
(rightmost)
largest
adjacency
position (directly
if equal)
(Action 1)
Decision making is more complex !
CS 2204 Spring 2014 Experiment 6 Appendices
Page 45
Lab 10
Block 6, Machine Play Block Development
1.
Start with the black box view where the outputs are fixed and the
input/output relationship
Example 2
a)
b)
c)
Understand the game rules and how the machine player has to interact
with the rest of the Ppm digital system
Determine the playing strategy (intelligence)
Determine the inputs
We know the game rules already !
There is an adjacency ?
N
?
Block 6
?
Play on the
(rightmost)
largest regular
reward position
(directly if
equal)
(Action 0)
Y
Play on the
(rightmost)
largest
adjacency
position (directly
if equal)
(Action 1)
CS 2204 Spring 2014 Experiment 6 Appendices
Page 46
Block 6, Machine Play Block Development
1.
Example 2
Lab 10
Start with the black box view where the outputs
are fixed and the input/output relationship
b)
Determine the playing strategy (intelligence)
Always plays (does not skip at all)
If there is no adjacency, it plays on the largest regular
reward points position directly or with an addition (chooses
direct playing if the two reward points are equal).
Otherwise, it plays on the largest regular adjacency position
directly or with an addition (chooses direct playing if
adjacencies are equal)
In either case, if two or more positions equally playable,
selects the rightmost one
If playing on the left side directly has the same
adjacency/regular reward points as playing on the right side
with addition, select playing on the left side directly
CS 2204 Spring 2014 Experiment 6 Appendices
Page 47
Block 6, Machine Play Block Development
1.
Example 2
Lab 10
Start with the black box view where the outputs are fixed
and the input/output relationship
c)
Determine the inputs
We have to collect eight regular reward points for eight possibilities
•
•
We have to collect eight adjacencies for eight possibilities
•
•
Four adjacencies on four displays with direct playing
Four adjacencies on four displays with additions
We will collect the eight regular reward points and eight adjacencies
sequentially
•
Four regular reward points on four displays with direct playing
Four regular reward points on four displays with additions
This will take 8 clock periods !
Then, we will play on a position in the ninth clock period
Player 2 spends
NINE P2clk
periods to think
CS 2204 Spring 2014 Experiment 6 Appendices
Page 48
Block 6, Machine Play Block Development
1.
Example 2
Lab 10
Start with the black box view where the outputs are fixed
and the input/output relationship
a)
b)
c)
Understand the game rules and how the machine player has to
interact with the rest of the Ppm digital system
Determine the playing strategy (intelligence)
Determine the inputs
We need to collect the regular reward points : RWD
We need to collect the adjacencies : NSD
We will collect eight regular
reward points sequentially
We have to input : P2sturn,
Clearp2ffs, P2clk
?
Block 6
?
CS 2204 Spring 2014 Experiment 6 Appendices
Page 49
Block 6, Machine Play Block Development
1.
Example 2
Lab 10
Start with the black box view where the outputs are fixed
and the input/output relationship
a)
b)
c)
Understand the game rules and how the machine player has to
interact with the rest of the Ppm digital system
Determine the playing strategy (intelligence)
Determine the inputs
We input RWD, NSD
We input P2sturn,
Clearp2ffs, P2clk
8
RWD
NSD
P2sturn
2
Block 6
?
Clearp2ffs
P2clk
CS 2204 Spring 2014 Experiment 6 Appendices
Page 50
Block 6, Machine Play Block Development
1.
Example 2
Lab 10
Start with the black box view where the outputs are fixed
and the input/output relationship
a)
b)
c)
Understand the game rules and how the machine player has to
interact with the rest of the Ppm digital system
Determine the playing strategy (intelligence)
Determine the inputs
The outputs are fixed !
8
RWD
NSD
P2sturn
Clearp2ffs
P2clk
4
2
P2SEL
P2add
Block 6
P2played
P2skip
8
P2CODE
We must connect 8 zeros to the P2CODE
lines to avoid unnecessary warnings
CS 2204 Spring 2014 Experiment 6 Appendices
Page 51
Block 6, Machine Play Block Development
Start with the black box view where the outputs are fixed and the
input/output relationship
Example 2
1.
Lab 10
•Must generate the seven outputs for correct operation
•The Ppm will stay in state 4 when the machine thinks : both P2played and P2skip are zero
•It stays in state 4 at least one Sysclk period
•The selection of inputs depends on the strategy and the implementation
CS 2204 Spring 2014 Experiment 6 Appendices
Page 52
Example 2
Block 6, Machine Play Block Development
Lab 10
2. Get the black box view with the inputs determined
and convert the textual input/output relationship
(including the playing strategy) to an operation
diagram
Sequential gather and Sequential compare
An operation diagram is needed
•
•
•
Convert the playing strategy to major operations
Partition Block 6 into subblocks
Block 6 is a tiny digital system itself
The machine player takes several clock periods to make a decision
To get the operation diagram, check the playing strategy and
determine what to do when :
All actions happen in the last state
Some actions indicate which data to collect
All conditions indicate what to collect
CS 2204 Spring 2014 Experiment 6 Appendices
Page 53
Lab 10
Block 6, Machine Play Block
Development
IG
P2st1
Determine position 1 regular reward and adjacency with direct playing, keep
each if it is larger & record the position number
IG
P2st2
Determine position 2 regular reward and adjacency with direct playing, keep
each if it is larger & record the position number
IG
P2st3
Determine position 0 regular reward and adjacency with direct playing &
record the position number
Determine position 3 regular reward and adjacency with direct playing, keep
each if it is larger & record the position number
IG
P2st4
P2st0
4
Determine position 0 regular reward and adjacency with an addition, keep
each if it is larger & record the position number
IG
P2st5
Convert the textual
input/output relationship
(including the playing strategy)
to an operation diagram
Determine position 1 regular reward and adjacency with an addition, keep
each if it is larger & record the position number
IG
P2st6
Example 2
2.
Determine position 2 regular reward and adjacency with an addition, keep
each if it is larger & record the position number
IG
P2st7
Determine position 3 regular reward and adjacency with an addition, keep
each if it is larger & record the position number
IG
4
RWD
8
Machine
Clearp2ffs
P2sturn
P2add
Player
P2played
P2clk
P2skip
Player 2 spends
NINE P2clk
periods to think
P2st8
NSD 2
P2SEL
Based on the stored information select the position to play
D
Player 2 plays on a position
CS 2204 Spring 2014 Experiment 6 Appendices
Page 54
P2st0
RTL Notation used
P2st1
Convert the operation diagram
to a high-level state diagram
with microoperations with the
same number of states
P2SEL = 0001 ; P2played = 0 ; P2skip = 0 ; P2add = 0 ; LRGRWD RWD
; LRGADJ NSD ; POSRWD 00001 ; POSNSD 00001
P2SEL = 0010 ; P2played = 0 ; P2skip = 0 ; P2add = 0 ;
If RWD > LRGRWD then LRGRWD RWD ; POSRWD 00010
If NSD > LRGNSD then LRGNSD NSD ; POSNSD 00010
P2st2
Example 2
3.
4
Lab 10
P2SEL = 0100 ; P2played = 0 ; P2skip = 0 ; P2add = 0 ;
If RWD > LRGRWD then LRGRWD RWD ; POSRWD 0100
If NSD > LRGNSD then LRGNSD NSD ; POSNSD 0100
P2st3
Block 6, Machine Play Block
Development
P2SEL = 1000 ; P2played = 0 ; P2skip = 0 ; P2add = 0 ;
If RWD > LRGRWD then LRGRWD RWD ; POSRWD 01000
If NSD > LRGNSD then LRGNSD NSD ; POSNSD 01000
4
RWD
8
Clearp2ffs
P2add
Player
P2st5
P2sturn
P2st4
Machine
P2played
P2st6
P2clk
P2SEL = 0001 ; P2played = 0 ; P2skip = 0 ; P2add = 1 ;
If RWD > LRGRWD then LRGRWD RWD ; POSRWD 10001
If NSD > LRGNSD then LRGNSD NSD ; POSNSD 10001
P2SEL = 0010 ; P2played = 0 ; P2skip = 0 ; P2add = 1 ;
If RWD > LRGRWD then LRGRWD RWD ; POSRWD 10010
If NSD > LRGNSD then LRGNSD NSD ; POSNSD 10010
P2SEL = 0100 ; P2played = 0 ; P2skip = 0 ; P2add = 1 ;
If RWD > LRGRWD then LRGRWD RWD ; POSRWD 10100
If NSD > LRGNSD then LRGNSD NSD ; POSNSD 10100
P2skip
Player 2 spends
NINE P2clk
periods to think
P2st7
NSD 2
P2SEL
P2SEL = 1000 ; P2played = 0 ; P2skip = 0 ; P2add = 1 ;
If RWD > LRGRWD then LRGRWD RWD ; POS 11000
If NSD > LRGNSD then LRGNSD NSD ; POSNSD 11000
P2st8
P2played = 1 ; P2skip = 0
If LRGNSD >0 then P2SEL = POSNSD[3:0] ; P2add = POSNSD[4] ;
else P2SEL = POSRWD[3:0] ; P2add = POSRWD[4]
Player 2 plays on a position
CS 2204 Spring 2014 Experiment 6 Appendices
Page 55
Lab 10
Block 6, Machine Play Block Development
4. From the high-level state diagram, obtain the datapath
P2clk
C
D1
Test2
D2
Test3
D3
TestAdd D4
Storensd
P2clk
Clr
CE
POSNSD0
Q1
POSNSD1
Q2
C
POSNSD2
Q3 POSNSD3
Q4 P2B
CE
P2clk
C
LRGRWD
Test1
D1
Test2
D2
Test3
D3
TestAdd D4
Storerwd
P2clk
Clr
CE
POSRWD
Q 8
D0
5-bit
Register
Storerwd
A>B
Gtnsd
B
LRGNSD1
Adj
LRGNSD0
Clr
Test0
8
2
CLR
Information Gathering
D
2
LRGNSD
CLR
RWD
A
NSD
2-bit
Comparator
LRGNSD
Test1
Q0
C
Q0
POSRWD0
Q1
POSRWD1
A
RWD
Q2
POSRWD2
8-bit
Comparator
CE
Q 2
D0
POSNSD
Storensd
Test0
5-bit
Register
2
2-bit
LRGNSD
Register
D
NSD
8-bit
LRGRWD
Register
Example 2
Datapath
8
LRGRWD
Q3 POSRWD3
8
A>B
Gtrwd
B
Q4 P2A
CLR
CLR
Clr
CS 2204 Spring 2014 Experiment 6 Appendices
Page 56
Lab 10
Block 6, Machine Play Block Development
4. From the high-level state diagram, obtain the datapath
Decision Making
A0
Y0
POSNSD0
B0
POSRWD1
A1
Test0
Test1
Y1
POSNSD1
B1
POSRWD2
A2
POSNSD2
POSRWD3
B2
5-bit
2-to-1 MUX
Example 2
POSRWD0
Datapath
Test2
P2SEL0
P2SEL1
P2SEL2
Y2
Test3
P2SEL3
A3
Y3
POSNSD3 B3
P2A
A4
Y4
P2B
Adj
TestAdd
P2add
B4
Sel
P2played
E
Play
P2skip
Play
0
CS 2204 Spring 2014 Experiment 6 Appendices
Page 57
Lab 10
Block 6, Machine Play Block Development
4. From the high-level state diagram, obtain the datapath
Example 2
Datapath
Information Gathering
Decision Making
CS 2204 Spring 2014 Experiment 6 Appendices
Page 58
Lab 10
Block 6, Machine Play Block Development
5.
From the high-level state diagram and the datapath, obtain the low-level state diagram
P2st0
P2st1
Test2 = 1 ; TestAdd = 0 ;
If Gtrwd == 1 then Storerwd = 1 ;
If Gtnsd == 1 then Storensd = 1
Test1 = 1 ; TestAdd = 1 ;
If Gtrwd == 1 then Storerwd = 1 ;
If Gtnsd == 1 then Storensd = 1
Test2 = 1 ; TestAdd = 1 ;
If Gtrwd == 1 then Storerwd = 1 ;
If Gtnsd == 1 then Storensd = 1
Test3 = 1 ; TestAdd = 1 ;
If Gtrwd == 1 then Storerwd = 1
If Gtnsd == 1 then Storensd = 1
P2st8
P2st4
Test0 = 1 ; TestAdd = 1 ;
If Gtrwd == 1 then Storerwd = 1 ;
If Gtnsd == 1 then Storensd = 1
P2st5
Test3 = 1 ; TestAdd = 0 ;
If Gtrwd == 1 then Storerwd = 1 ;
If Gtnsd == 1 then Storensd = 1
P2st6
P2st3
Test1 = 1 ; TestAdd = 0 ;
If Gtrwd == 1 then Storerwd = 1 ;
If Gtnsd == 1 then Storensd = 1
P2st2
Test0 = 1; TestAdd = 0 ;
Storerwd = 1 ; Storensd = 1
P2st7
Example 2
4
Play = 1
Player 2 plays on a position
CS 2204 Spring 2014 Experiment 6 Appendices
Page 59
Block 6, Machine Play Block Development
6.
Lab 10
Decide about how to implement the control unit (sequencer)
Sequential gather and Sequential compare
Example 2
Nine control signals
Two status signals
Hardwiring or microprogramming ?
•
Hardwiring is acceptable if it is not a complex digital system : It is the case with the Ppm term project
4
8
Datapath
RWD
2
NSD
P2SEL
Gather reward points & adjacencies & compare them
Select one based on the adjacency ≡ Make a decision
P2clk
P2played
P2skip
Gtrwd
Gtnsd
P2add
Storensd
Play
Storerwd
Clr
Test3
Test2
Test1
Test0
TestAdd
P2clk
Clearp2ffs
Control Unit
P2sturn
CS 2204 Spring 2014 Experiment 6 Appendices
Page 60
Hardwiring or microprogramming ?
Hardwiring is acceptable if it is not a complex digital system : It is the case
with the Ppm term project
•
Example 2
Block 6, Machine Play Block Development
Sequential gather and Sequential compare
4
Test1 = 1 ; TestAdd = 0 ;
If Gtrwd == 1 then Storerwd = 1 ;
If Gtnsd == 1 then Storensd = 1
Test0 = 1; TestAdd = 0 ;
Storerwd = 1 ; Storensd = 1
Test2 = 1 ; TestAdd = 0 ;
If Gtrwd == 1 then Storerwd = 1 ;
If Gtnsd == 1 then Storensd = 1
Test2 = 1 ; TestAdd = 1 ;
If Gtrwd == 1 then Storerwd = 1 ;
If Gtnsd == 1 then Storensd = 1
Test1 = 1 ; TestAdd = 1 ;
If Gtrwd == 1 then Storerwd = 1 ;
If Gtnsd == 1 then Storensd = 1
Test0 = 1 ; TestAdd = 1 ;
If Gtrwd == 1 then Storerwd = 1 ;
If Gtnsd == 1 then Storensd = 1
P2st8
Player 2 plays on a position
Play = 1
Test3 = 1 ; TestAdd = 1 ;
If Gtrwd == 1 then Storerwd = 1
If Gtnsd == 1 then Storensd = 1
P2st4
Test3 = 1 ; TestAdd = 0 ;
If Gtrwd == 1 then Storerwd = 1 ;
If Gtnsd == 1 then Storensd = 1
P2st1
P2st0
P2st2
P2st5
P2st3
P2st6
P2st7
Lab 10
6. Decide about how to implement the control unit (sequencer)
Page 61
CS 2204 Spring 2014 Experiment 6 Appendices
Sequential gather and Sequential compare
Design the hardwired sequencer
A counter + decoder combination is
needed to keep track of the states
Example 2
Implement the sequencer which is treated as a state machine
7.
4
Test1 = 1 ; TestAdd = 0 ;
If Gtrwd == 1 then Storerwd = 1 ;
If Gtnsd == 1 then Storensd = 1
Test0 = 1; TestAdd = 0 ;
Storerwd = 1 ; Storensd = 1
Test2 = 1 ; TestAdd = 0 ;
If Gtrwd == 1 then Storerwd = 1 ;
If Gtnsd == 1 then Storensd = 1
Test2 = 1 ; TestAdd = 1 ;
If Gtrwd == 1 then Storerwd = 1 ;
If Gtnsd == 1 then Storensd = 1
Test1 = 1 ; TestAdd = 1 ;
If Gtrwd == 1 then Storerwd = 1 ;
If Gtnsd == 1 then Storensd = 1
Test0 = 1 ; TestAdd = 1 ;
If Gtrwd == 1 then Storerwd = 1 ;
If Gtnsd == 1 then Storensd = 1
P2st8
Player 2 plays on a position
Play = 1
Test3 = 1 ; TestAdd = 1 ;
If Gtrwd == 1 then Storerwd = 1
If Gtnsd == 1 then Storensd = 1
P2st4
Test3 = 1 ; TestAdd = 0 ;
If Gtrwd == 1 then Storerwd = 1 ;
If Gtnsd == 1 then Storensd = 1
P2st1
P2st0
P2st2
P2st5
P2st3
P2st6
P2st7
Lab 10
Block 6, Machine Play Block Development
Page 62
CS 2204 Spring 2014 Experiment 6 Appendices
Lab 10
Block 6, Machine Play Block Development
7.
Implement the sequencer which is treated as a state machine
Sequential gather and Sequential compare
Design the hardwired sequencer
Example 2
Test0
4-bit up counter
CE
P2s8
P2clk
P2streg
C
Q0
P2streg0
Q1
P2streg1
Q2
P2streg2
A1
A2
Q3
P2streg3
D0
P2s0
D1
P2s1
D2
P2s2
D3
P2s3
D4
P2s4
D5
P2s5
D6
P2s6
D7
P2s7
Test2 Test3 TestAdd Play Clr
E1
P2sturn
Clearp2ffs
A0
3-to-8 Decoder
P2sturn
Test1
Clearp2ffs
E0
P2s8
CLR
Use this counter+decoder circuit
if your machine player does not
skip and has nine states
P2s8
Storerwd
Storensd
P2s8
P2s8
P2s0
P2s0
Gtrwd
Gtnsd
P2streg2
CS 2204 Spring 2014 Experiment 6 Appendices
Page 63
Lab 10
Block 6, Machine Play Block Development
Start implementing the circuits of Block 6 on computer
•
Sequential gather and Sequential compare
Final digital system design on paper
Datapath
Example 2
Information
Gathering
Decision
Making
Control Unit
CS 2204 Spring 2014 Experiment 6 Appendices
Page 64
Block 6, Machine Play Block Development
Lab 10
Start implementing the circuits of Block 6 on computer
Example 2
• Sequential gather and Sequential compare
Copy the termproject folder and paste it as exp6
Start drawing the schematics by using the design on paper
Perform simulations
CS 2204 Spring 2014 Experiment 6 Appendices
Page 65
Lab 10
Analysis of the Term Project
Polytechnic Playing Machine, Ppm
The term project is human vs. machine
The black-box view
From the input devices
13
19
Ppm
To the output devices
Figure 1. The Ppm black box view.
From page 2 of the Term Project Handout
CS 2204 Spring 2014 Experiment 6 Appendices
Page 66
Lab 10
Block 6, Machine Play Block Development
Plays as the machine player
On paper
1.
Start with the black box view where the outputs are fixed and the
input/output relationship
a)
Lab 9/10
b)
c)
2.
Understand the game rules and how the machine player has to interact
with the rest of the Ppm digital system
Determine the playing strategy (intelligence)
Determine the inputs
Convert the black box view with the inputs determined and the
textual input/output relationship (including the playing strategy) to
an operation diagram
•
•
•
•
3.
How can we implement the block ?
Convert the playing strategy to major operations
Partition Block 6 into subblocks
Operation diagram implies the machine player goes through steps taking
several clock periods
The operation diagram also implies that the Block 6 is a tiny digital system
itself
Convert the operation diagram to a high-level state diagram with
microoperations with the same number of states
•
•
A diagram with finite number of states
Distribute microoperations to states
CS 2204 Spring 2014 Experiment 6 Appendices
Page 67
Block 6, Machine Play Block Development
On paper
4.
From the high-level state diagram, obtain the datapath
Lab 9/10
•
•
•
5.
6.
Design the sequencer
Start moving the circuits of Block 6 to the computer
Hardwiring or microprogramming
Hardwiring is acceptable if it is not a complex digital system : It is
the case with the Ppm term project
Implement the sequencer which is treated as a state machine
Continue to partition the datapath into subblocks
Design each (sub)block
Implement microperations in datapath hardware
From the high-level state diagram and the datapath, obtain the
low-level state diagram
Decide about how to implement the control unit (sequencer)
7.
Lab 11-13
Lab 10
Copy the termproject folder and paste it as exp6
Start drawing the schematics by using the design on paper
Label the components
CS 2204 Spring 2014 Experiment 6 Appendices
Page 68
Lab 9-10
Block 6, Machine Play Block Development
1.
Lab 10
Start with the black box view where the outputs are fixed and the
input/output relationship
a) Understand the game rules and how the machine player has to
interact with the rest of the Ppm digital system
b) Determine the playing strategy (intelligence)
•
How to determine of the machine player strategy is acceptable ?
At least
3 (three)
different complex conditions
At least
4 (four)
different complex actions
CS 2204 Spring 2014 Experiment 6 Appendices
Page 69
Lab 9-10
Lab 10
Block 6, Machine Play Block Development
1.
Start with the black box view where the outputs are fixed and the
input/output relationship
a)
Understand the game rules and how the machine player has to interact with the
rest of the Ppm digital system
b) Determine the playing strategy (intelligence)
•
How to determine of the machine player strategy is acceptable ?
At least 3 (three) different
complex conditions
Player 1 has more points than Player 2 ?
There is an adjacency & RD is not zero ?
Other complex conditions
are possible
There is a position with a 0 & RD is
not zero & next RD not equal to RD ?
Player 1 does not have (64)10 or more points &
the largest regular reward is less than (64)10
Player 1 does not have (64)10 or more points &
there is a position with a zero and RD is not zero
CS 2204 Spring 2014 Experiment 6 Appendices
Page 70
Lab 10
Block 6, Machine Play Block Development
1.
Start with the black box view where the outputs are fixed and the
input/output relationship
a)
Understand the game rules and how the machine player has to interact with the
rest of the Ppm digital system
b) Determine the playing strategy (intelligence)
•
How to determine of the machine player strategy is acceptable ?
Lab 9-10
At least 4 (four) different
complex actions
Other complex
actions are possible
Play on the
(rightmost if
equal) largest
regular
reward
position
(directly if
equal)
Play on the
(rightmost if
equal) largest
display
position with
an addition
Play on the
(rightmost if
equal) largest
adjacency
position
(directly if
equal)
Play on
the
(rightmost)
zero
position
directly
Play on the (rightmost
if equal) adjacency
position that results
in the most regular
reward points
(directly if equal)
CS 2204 Spring 2014 Experiment 6 Appendices
Page 71
Lab 9-10
Block 6, Machine Play Block Development
1.
Lab 10
Start with the black box view where the outputs are fixed and
the input/output relationship
b) Determine the playing strategy (intelligence)
Non-intelligent machine player strategies
1.
2.
3.
Play in a permanently fixed way : always play on the rightmost position
which does not have a display overflow. If all positions result in display
overflows, skips
Play randomly : when it is time to play, stop a freely running 2-bit counter
and play on that position
Play in a fixed way-round robin fashion : every time it is the turn,
increment a 2-bit counter and play on that position
Do not implement these strategies
CS 2204 Spring 2014 Experiment 6 Appendices
Page 72
Lab 9-10
Block 6, Machine Play Block Development
1.
Lab 10
Start with the black box view where the outputs are fixed and the
input/output relationship
b) Determine the playing strategy (intelligence)
•
How to determine of the machine player strategy is acceptable ?
If you do not specify the secondary strategy for
even a single action, it means the machine player
does not work and so you will lose 30 points
CS 2204 Spring 2014 Experiment 6 Appendices
Page 73
Lab 9-10
Lab 10
Block 6, Machine Play Block Development
2. Convert the textual input/output relationship (including the
playing strategy) to an operation diagram
Decide about the parallel/sequential implementation issue
Get the subblocks
Convert the playing strategy to major operations
3. Convert the operation diagram to a high-level state diagram
with microoperations with the same number of states
If sequential gather and Sequential compare+decide is decided
A diagram with finite number of states
Distribute microoperations to states
CS 2204 Spring 2014 Experiment 6 Appendices
Page 74
Lab 9-10
Lab 10
Block 6, Machine Play Block Development
4. From the high-level state diagram, obtain the datapath
Sequential gather and Sequential compare+decide
Design each (sub)block
Implement microperations in datapath hardware
5. From the high-level state diagram and the datapath, obtain
the low-level state diagram
If Sequential gather and Sequential compare+decide is chosen
6. Decide about how to implement the control unit (sequencer)
Hardwiring or microprogramming ? Choose hardwiring
7. Implement the sequencer which is treated as a state machine
Design the sequencer
Use the 5-state or 9-state counter+decoder combinations given
on previous slides
Make sure the machine player takes
at least 9 clock periods to play
CS 2204 Spring 2014 Experiment 6 Appendices
Page 75
Lab 11-13
Block 6, Machine Play Block Development
Lab 10
Move the design to the computer ≡ Implement
Block 6 on computer
Plan where to place the subblocks on the screen
Delete your Block 6 circuits if they are not needed
Start drawing the schematics
First place the components, then their outputs and then their
inputs
Label the components
Save schematic 6, ppm6.sch
CS 2204 Spring 2014 Experiment 6 Appendices
Page 76
Lab 11-13
Block 6, Machine Play Block Development
Lab 10
Move the design to the computer ≡ Implement
Block 6 on computer
Start drawing the schematics
Make sure your circuits in Block 6 follow
the Term Project Check List handout
DO NOT IMPLEMENT INFORMATION GATHERING
CIRCUITRY COMBINATIONALLY
USE available circuits in Blocks 1, 2, 3, 4 and 5
CS 2204 Spring 2014 Experiment 6 Appendices
Page 77
Lab 11-13
Block 6, Machine Play Block Development
Lab 10
Move the design to the computer ≡ Implement
Block 6 on computer
Start drawing the schematics
Your machine player would not work completely because of
three reasons
It does not follow the game rules
It does not follow your playing strategy
Your playing strategy is not complete
CS 2204 Spring 2014 Experiment 6 Appendices
Page 78
Lab 11-13
Block 6, Machine Play Block Development
Lab 10
Move the design to the computer ≡ Implement
Block 6 on computer
Remember also the following
• Follow all the suggestions and warnings, including the
timetable !
• Follow the 7-step procedure to design Block 6 !
• Start debugging Block 6 starting with the outputs,
proceeding backward
• Make sure everybody has everything related to Block 6
all the time
• Do not have black boxes (macros)
• Only six schematics in the projects
• TAs and I will not answer design related questions !
• Experiment 6 is like an exam : It must be your work !
• No communication with other teams !
CS 2204 Spring 2014 Experiment 6 Appendices
Page 79
Lab 11-13
Lab 10
Block 6, Machine Play Block Development
Implementing the machine player, Block 6
Every member of a team must do the schematic design to
remember better for the final exam
The timetable for the rest of the semester
Students will submit the Experiment 6 project which will
include the implementation of
• Block 6
The deadline : 6:50 PM, Friday, May 2, 2014
When it is 6:50 on Friday, May 2, 2014
We will ask students to stop designing the circuits
Then, we will collect the projects
Submit your Experiment 6 during a lab session !
CS 2204 Spring 2014 Experiment 6 Appendices
Page 80
Make sure you have the LABS account and see the S drive
Make sure you have installed WebPACK 12.4 on your laptop
Make sure you create a CS2204 folder on both
Read slides at the end to learn about the software, Project Manager,
Schematic design and other related topics
Do not leave the lab before your partners finish
► Help your partners
QUESTIONS ?
Continue
reading the
Term
Project
handout
Digital
Logic
and
State Machine Design
Think about
the machine
player
strategy
CS 2204 Spring 2014 Experiment 6 Appendices
Page 81
CS 2204
Lab 11
Digital Logic
and
State Machine Design
Appendices
Labs 9, 10, 11, 12, 13
Experiment 6
?
Spring 2014
Appendices Labs 10 - 12 Outline
Lab 11
Presentation
Machine Player Example 2 (Lab 10)
Digital product development overview (Lab 11)
Component selection for a new chip
• Xilinx component usage
Component selection for a new PCB
• TTL LS SSI chip usage
Semiconductor technology overview (Lab 12)
Submitting the term project
Submitting the term project (Lab 13)
Individual work
Developing Ppm Block 6
CS 2204 Spring 2014 Experiment 6 Appendices
Page 83
Developing a new chip
1) Development Cycle on Computers
DESIGN
TEST
MODIFY
Major error : Redesign
Major error : Redesign or terminate the project due to TTM
2) Development Cycle with FPGA chips
Mount
Test
Modify
Major error : Redesign or terminate the project due to TTM
3) Development Cycle on prototype chip
Fabricate
Test
Lab 11
Which components and how many ?
TEST : Apply input combinations, test
vectors, and simulate
During testing If you see MODIFYING
hardware to optimize it is possible, do
that after you correct logic and timing
errors. Then, test again to see if your
minimization has logic/timing errors
Mount : FPGAs are mounted on
bread/boards, wired and programmed
Test : apply test vectors to FPGAs
Modify : either FPGA mounting/wiring
is changed or a simple design change is
made on computers, simulated, then
FPGAs are programmed and tested
Fabricate chip by sending a GDSII file
to a fabrication facility : tape out
Apply test vectors to the chip
Chip
CS 2204 Spring 2014 Experiment 6 Appendices
Page 84
Developing a digital product
Lab 11
A new chip
Which gates/FFs and how many is determined by
The application (major operations)
Available components of the technology chosen
Besides speed, cost, power, etc. : design goals
CS 2204 Spring 2014 Experiment 6 Appendices
Page 85
Lab 11
CS2204 Components
Available components for a new chip
Use these
Generic components
as much
as possible Lectures, homework, exams
Flip-flops Popular digital circuits
AND
D
OR
JK
NOT
T
NAND
SR
NOR
…
…
To save time,
space, power.
weight,…
ADDer
Comparator
Multiplexer
DeMux
Decoder
Encoder
ALU
Counter
Register
…
High-density components
Gates
Xilinx components
Labs
Gates
AND
OR
NOT
NAND
NOR
…
Flip-flops
D
T
JK
Popular digital circuits
ADDer
Comparator
Multiplexer
DeMux
Decoder
Encoder
ALU
Counter
Register
…
CS 2204 Spring 2014 Experiment 6 Appendices
Page 86
Lab 11
Implementing a Combinational Circuit on a New Chip
By using generic components that are AND, OR, NOT,…
The 2-to-1 MUX
Which generic components ?
1 generic inverter
2 generic 2-input AND gates
1 generic 2-input OR gate
a
Total : 4 generic components used
NOT
b
AND
OR
c
a
AND
y(a, b, c) = a.b + a.c
CS 2204 Spring 2014 Experiment 6 Appendices
Page 87
Lab 11
Implementing a Combinational Circuit on a New
Chip
By using generic components that are AND, OR, NOT
The 2-to-1 MUX
Use a generic 2-to-1 MUX already designed
Do not design your own 2-to-1 MUX
a
NOT
b
AND
OR
c
a
AND
y(a, b, c) = a.b + a.c
CS 2204 Spring 2014 Experiment 6 Appendices
Page 88
Implementing a Combinational Circuit on a New Chip
Lab 11
The 2-to-1 MUX
Use a generic 2-to-1 MUX already designed
a
Sel
c
1
b
0
Which generic components ?
2-to-1
MUX
y
1 generic 2-to-1 MUX
Total : 1 generic component used
a
NOT
b
AND
OR
c
a
AND
y(a, b, c) = a.b + a.c
CS 2204 Spring 2014 Experiment 6 Appendices
Page 89
Implementing a Combinational Circuit on a New Chip
Lab 11
By using generic components that are AND, OR, NOT,…
Which generic components ?
a
ab
2 generic inverters
5 generic 2-input AND gates
1 generic 5-input OR gate
b
a
ad
d
z
d
a
Total : 8 generic components used
ac
c
ab + ad + ac + c d + b c
c
c
cd
Output z = 1 if (a,b) > (c, d)
d
b
bc
c
2-bit Unsigned Binary Comparator
From Handout 3
CS 2204 Spring 2014 Experiment 6 Appendices
Page 90
Implementing a Combinational Circuit on a New Chip
Lab 11
By using generic components that are AND, OR, NOT,…
2-bit
Unsigned Binary Comparator
Use a generic comparator already designed
You need an extra NOT gate besides the comparator
Do not design your own Comparator
a
ab
b
a
ad
d
z
d
a
ac
c
c
c
cd
d
b
bc
c
CS 2204 Spring 2014 Experiment 6 Appendices
Page 91
Implementing a Combinational Circuit on a New Chip
Lab 11
2-bit Unsigned Binary Comparator
a
A1
By using a generic comparator already designed
b
c
A0
B1
d
B0
2-bit Unsigned Binary Comparator
Which generic components ?
1 generic 2-bit Unsigned Comparator
1 generic NOT gate
Total : 2 generic components used
AGTB
AEQB
ALTB
z
Output z = 1 if (a,b) > (c, d)
CS 2204 Spring 2014 Experiment 6 Appendices
Page 92
Implementing a Sequential Circuit on a New Chip
Lab 11
By using generic components that are D, J-K, AND, OR, NOT,…
y1
The sequence detector from Handout 17
most significant FF
y0
J
y0
y1
y2
Q
C
K
clock
y2
x
y0
J
x
y0
K
x
y0
Q
y2
x
y0
Q
y1
C
clock
y2
Least significant FF
x
y2
J
y0
x
y1
y2
K
C
1 generic inverter
4 generic 2-input AND gates
6 generic 3-input AND gates
1 generic 4-input AND gate
4 generic 2-input OR gates
2 generic 3-input OR gates
3 generic positive-edge triggered J-K FFs
Q
Q
Which generic components ?
x
Total : 21 generic components used
y1
y0
y1
clock
y2
x
x
Q
x
y2
y2
y0
y1
y2
x
z
Try to convert
the problem to
a problem with
registers,
counters and
shift registers
CS 2204 Spring 2014 Experiment 6 Appendices
Page 93
Implementing a Combinational Circuit on a New Chip
Lab 11
By using generic components that are D, J-K, AND, OR, NOT,…?
The sequence detector from Handout 17
There is no such generic sequence detector
We have to design our own sequence detector
y1
y0
most significant FF
x
J
y0
y1
Q
y2
Q
C
K
clock
y2
The design with
21 components
is implemented
x
y0
J
x
y0
y0
y2
x
y0
Q
C
K
x
Q
y1
y1
clock
y2
Least significant FF
x
y2
J
x
y1
y2
K
C
y1
Q
y0
x
y2
y0
Q
y0
y1
y2
y2
y2
x
x
x
z
But still, try to use
registers/counters/
shift registers with
a few gates
clock
CS 2204 Spring 2014 Experiment 6 Appendices
Page 94
CS2204 Components
Lab design
Lab 11
Available components for a new chip
Gates Flip-flops
AND
OR
NOT
NAND
NOR
…
D
JK
T
SR
Popular digital circuits
ADDer
Comparator
Multiplexer
DeMux
Decoder
Encoder
ALU
Counter
Register
…
Xilinx components
Labs
Gates Flip-flops Popular digital circuits
AND
OR
NOT
NAND
NOR
…
D
T
JK
Try not to use
these components
ADDer
Comparator
Multiplexer
DeMux
Decoder
Encoder
ALU
Counter
Register
…
CS 2204 Spring 2014 Experiment 6 Appendices
High-density components
Generic components
Lectures, homework, exams
Use Xilinx macros
as much as possible
Page 95
Lab 11
Implementing a Combinational Circuit on a New Chip
By using Xilinx components that are AND, OR, NOT,…
The 2-to-1 MUX
1 inverter, INV
2 2-input AND gates, AND2
1 2-input OR gate, OR2
Which Xilinx components ?
Total : 4 Xilinx components used
a
NOT
b
AND
OR
c
a
AND
y(a, b, c) = a.b + a.c
CS 2204 Spring 2014 Experiment 6 Appendices
Page 96
Lab 11
Implementing a Combinational Circuit on a New
Chip
By using Xilinx components that are AND, OR, NOT,…
The 2-to-1 MUX
Xilinx already has 2-to-1 MUXes
Use them
Do not design your own 2-to-1 MUX
a
NOT
b
AND
OR
c
a
AND
y(a, b, c) = a.b + a.c
CS 2204 Spring 2014 Experiment 6 Appendices
Page 97
Implementing a Combinational Circuit on a New Chip
Lab 11
The 2-to-1 MUX
Xilinx already has 2-to-1 MUX macros
M2_1
Which Xilinx components ?
1 Xilinx M2_1 MUX
a
Total : 1 Xilinx component used
NOT
b
AND
OR
c
a
AND
y(a, b, c) = a.b + a.c
CS 2204 Spring 2014 Experiment 6 Appendices
Page 98
Implementing a Combinational Circuit on a New Chip
Lab 11
By using Xilinx components that are AND, OR, NOT,…
Which Xilinx components ?
a
2 inverters, INV
5 2-input AND gates, AND2
1 5-input OR gate, OR5
ab
b
a
Total : 8 Xilinx components used
ad
d
z
d
a
ac
c
c
c
cd
ab + ad + ac + c d + b c
Output z = 1 if (a,b) > (c, d)
d
b
c
bc
2-bit Unsigned Binary Comparator
From Handout 3
CS 2204 Spring 2014 Experiment 6 Appendices
Page 99
Implementing a Combinational Circuit on a New Chip
Lab 11
By using Xilinx components that are AND, OR, NOT,…
2-bit
Unsigned Binary Comparator
Use them
Xilinx already has Comparators
You need an extra NOT gate besides the comparator
Do not design your own Comparator
a
ab
b
a
ad
d
z
d
a
ac
c
c
c
cd
d
b
bc
c
CS 2204 Spring 2014 Experiment 6 Appendices Page 100
Implementing a Combinational Circuit on a New Chip
Lab 11
2-bit Unsigned Binary Comparator
By using Xilinx comparators
1 2-bit Comparator, COMPM2
1 NOT gate, INV
Total : 2 Xilinx components used
Which Xilinx components ?
Output z = 1 if (a,b) > (c, d)
CS 2204 Spring 2014 Experiment 6 Appendices Page 101
Implementing a Sequential Circuit on a New Chip
Lab 11
By using Xilinx components that are D, J-K, AND, OR, NOT,…
The sequence detector from Handout 17
y1
x
J
y0
y1
Q
y2
Q
C
K
clock
y2
x
y0
J
x
y0
y0
y2
x
y0
Q
C
K
x
Q
y1
clock
y2
Least significant FF
x
y2
J
y0
x
y1
y2
K
C
x
y1
y2
clock
Q
Which Xilinx components ?
y0
1 inverter, INV
4 2-input AND gates, AND2
6 3-input AND gates, AND3
1 4-input AND gate, AND4
4 2-input OR gates, OR2
2 3-input OR gates, OR3
3 positive-edge triggered J-K FFs, FJKC
most significant FF
Total : 21 Xilinx components used
y1
y0
y2
y2
Q
y0
y1
y2
x
x
z
x
CS 2204 Spring 2014 Experiment 6 Appendices Page 102
Implementing a Combinational Circuit on a New Chip
Lab 11
By using Xilinx components that are D, J-K, AND, OR, NOT,…
The sequence detector from Handout 17
Xilinx does not have this sequence detector
We have to design our own sequence detector
y1
y0
most significant FF
x
J
y0
y1
Q
y2
Q
C
K
clock
y2
The design with
21 components
is implemented
x
y0
J
x
y0
y0
y2
x
y0
Q
C
K
x
Q
y1
y1
clock
y2
Least significant FF
x
y2
J
x
y1
y2
K
C
y1
Q
y0
x
y2
y0
Q
y0
y1
y2
y2
y2
x
x
x
z
But still, try to use
registers/counters/
shift registers with
a few gates
clock
CS 2204 Spring 2014 Experiment 6 Appendices Page 103
Developing a new PCB
1) Development Cycle on Computers
Major error : Redesign
DESIGN
TEST
MODIFY
Major error : Redesign or terminate the project due to TTM
2) Dev. Cycle with off-the-shelf chips
Mount
Test
Modify
Major error : Redesign or terminate the project due to TTM
3) Dev. Cycle on prototype PCB
Fabricate
Test
Modify
PCB
Which chips and how many ?
Lab 11
TEST : Simulating by applying input
combinations, test vectors, may not be
possible. It may be coarse grain simulation
During testing if you see MODIFYING
hardware to optimize it is possible, do that
after you correct logic and timing errors.
Then, test again to see if your minimization
has logic/timing errors
Mount : Chips are mounted on
bread/boards and wired
Test : apply test vectors to the chips
Modify : chip mounting/wiring is changed
and tested or a simple design change is
made on computers, simulated, then chip
mounting/wiring is changed and tested
Fabricate PCB at a fabrication facility,
mount chips and other components
Apply test vectors to the PCB
Modify means chip mounting/wiring is
changed and tested
CS 2204 Spring 2014 Experiment 6 Appendices Page 104
Developing a digital product
Lab 11
A new PCB
Which chips and how many is determined by
The application (major operations)
Available chips of the technology chosen
Besides speed, cost, power, etc. : design goals
CS 2204 Spring 2014 Experiment 6 Appendices Page 105
Lab 11
CS2204 components
Available chips for a new PCB
Use these Generic chips
as much
Lectures, homework, exams
as possible
Flip-flops Popular digital circuits
AND
D
OR
JK
NOT
T
NAND
SR
NOR
…
…
To save time,
space, power.
weight,…
ADDer
Comparator
Multiplexer
DeMux
Decoder
Encoder
ALU
Counter
Register
…
High-density chips
Gates
TTL LS chips
Lectures, homework, exams
Gates
AND
OR
NOT
NAND
NOR
…
Flip-flops
D
JK
Popular digital circuits
ADDer
Comparator
Multiplexer
DeMux
Decoder
Encoder
ALU
Counter
Register
…
CS 2204 Spring 2014 Experiment 6 Appendices Page 106
CS2204 components
Available chips for a new PCB
Gates
AND
OR
NOT
NAND
NOR
…
Flip-flops Popular digital circuits
D
JK
T
SR
…
ADDer
Comparator
Multiplexer
DeMux
Decoder
Encoder
ALU
Counter
Register
…
Gates
AND
OR
NOT
NAND
NOR
…
Flip-flops
D
JK
Try not to use
these SSI chips
Popular digital circuits
ADDer
Comparator
Multiplexer
DeMux
Decoder
Encoder
ALU
Counter
Register
…
MSI, LSI chips
Generic chips
Lectures, homework, exams
TTL LS chips
Lectures, homework, exams
High-density chips
Lab 11
Use higher density chips
(MSI, LSI) as much as
possible
CS 2204 Spring 2014 Experiment 6 Appendices Page 107
Try not
use SSI chips
TTL LS SSI Chips Used
Thisto
Semester
Lab 11
They have less than 10 gates according to the A Brief Look at
Semiconductor Technology handout
NAND-Gate Chips
74LS00 4 2-input NAND gates
74LS10 3 3-input NAND gates
74LS20 2 4-input NAND gates
74LS30 1 8-input NAND gate
From ON Semiconductor
LS TTL Data Manual
From Texas Instruments
Digital Logic Data Book
CS 2204 Spring 2014 Experiment 6 Appendices Page 108
Try not
use SSI chips
TTL LS SSI Chips Used
Thisto
Semester
Lab 11
They have less than 10 gates according to the A Brief Look at
Semiconductor Technology handout
NOR-Gate Chips
74LS02 4 2-input NOR gates
74LS27 3 3-input NOR gates
From Texas Instruments
Digital Logic Data Book
CS 2204 Spring 2014 Experiment 6 Appendices Page 109
Try not
use SSI chips
TTL LS SSI Chips Used
Thisto
Semester
Lab 11
They have less than 10 gates according to the A Brief Look at
Semiconductor Technology handout
Inverter-Gate Chips
74LS04 6 inverters
From ON Semiconductor
LS TTL Data Manual
CS 2204 Spring 2014 Experiment 6 Appendices Page 110
Try not
use SSI chips
TTL LS SSI Chips Used
Thisto
Semester
Lab 11
They have less than 10 gates according to the A Brief Look at
Semiconductor Technology handout
AND-Gate Chips
74LS08 4 2-input AND gates
74LS11 3 3-input AND gates
74LS21 2 4-input AND gates
From ON Semiconductor
LS TTL Data Manual
From Texas Instruments
Digital Logic Data Book
CS 2204 Spring 2014 Experiment 6 Appendices
Page 111
Try not
use SSI chips
TTL LS SSI Chips Used
Thisto
Semester
Lab 11
They have less than 10 gates according to the A Brief Look at
Semiconductor Technology handout
OR-Gate Chips
74LS32 4 2-input OR gates
From ON Semiconductor
LS TTL Data Manual
CS 2204 Spring 2014 Experiment 6 Appendices Page 112
Try not
use SSI chips
TTL LS SSI Chips Used
Thisto
Semester
Lab 11
They have less than 10 gates according to the A Brief Look at
Semiconductor Technology handout
EX-OR-Gate Chips
74LS86 4 2-input EX-OR gates
From Texas Instruments
Digital Logic Data Book
CS 2204 Spring 2014 Experiment 6 Appendices Page 113
TTL LS SSI Chips Used
This
Try not
toSemester
use SSI chips
Lab 11
They have less than 10 gates according to the A
Brief Look at Semiconductor Technology handout
EX-NOR-Gate Chips
74LS266 4 2-input EX-NOR gates
From Texas Instruments
Digital Logic Data Book
CS 2204 Spring 2014 Experiment 6 Appendices
Page 114
Try not
use SSI chips
TTL LS SSI Chips Used
Thisto
Semester
Lab 11
They have less than 10 gates according to the A Brief Look at
Semiconductor Technology handout
AND-OR-Invert-Gate Chips
74LS51 Dual AOI Network
From Texas Instruments
Digital Logic Data Book
CS 2204 Spring 2014 Experiment 6 Appendices Page 115
Try This
not to
use SSI chips
TTL LS SSI Chips Used
Semester
Lab 11
They have less than 10 gates according to the A Brief Look at
Semiconductor Technology handout
D-FF Chips
74LS74 2 positive-edge triggered D Fs
From ON Semiconductor
LS TTL Data Manual
CS 2204 Spring 2014 Experiment 6 Appendices Page 116
Lab 11
Try not
toSemester
use SSI chips
TTL LS SSI Chips Used
This
They have less than 10 gates according to the A Brief Look at
Semiconductor Technology handout
J-K-FF Chips
74LS109 2 positive-edge triggered J-K Fs
K
From Texas Instruments
Digital Logic Data Book
CS 2204 Spring 2014 Experiment 6 Appendices
Page 117
Lab 11
Try not
toSemester
use SSI chips
TTL LS SSI Chips Used
This
They have less than 10 gates according to the A Brief Look at
Semiconductor Technology handout
J-K-FF Chips
74LS112 2 negative-edge triggered J-K Fs
From Texas Instruments
Digital Logic Data Book
CS 2204 Spring 2014 Experiment 6 Appendices
Page 118
Implementing a Combinational Circuit on a New PCB
By using TTL LS SSI chips with
OR,
NOT,…
gates
Try AND,
not to
use
SSI chips
a
The 2-to-1 MUX
Which TTL components ?
NOT
AND
b
OR
c
a
AND
Lab 11
We need :
1 inverter
2 2-input AND gates
1 2-input OR gate
y(a, b, c) = a.b + a.c
TTL LS SSI Chip Usage ?
1 74LS04 with 6 inverters, 5 inverters unused
1 74LS08 with 4 2-input AND gates, 2 gates unused
1 74LS32 with 4 2-input OR gates, 3 gates unused
Total : 3 chips used, 10 gates unused
CS 2204 Spring 2014 Experiment 6 Appendices Page 119
Implementing a Combinational Circuit on a New PCB
By using TTL LS SSI chips with
OR,
NOT,…
gates
Try AND,
not to
use
SSI chips
a
The 2-to-1 MUX
Lab 11
Which TTL components ?
We need :
4 2-input NAND gates
NAND
NAND
b
NAND
c
a
y(a, b, c) = a.b + a.c
NAND
TTL LS SSI Chip Usage ?
1 74LS00 with 4 2-input NAND gates, 0 gates unused
Total : 1 chip used, 0 gates unused
CS 2204 Spring 2014 Experiment 6 Appendices Page 120
Implementing a Combinational Circuit on a New PCB
Lab 11
The 2-to-1 MUX
Try not to use SSI chips to implement combinational circuits
Use higher density chips : 74LS157 TTL LS MSI chip : 4 2-to-1 MUXes
•
One chip has four 2-to-1 MUXes !
Which TTL components ?
0 bc 0 0 00 0 0
1 74LS157 4-bit 2-to-1 MUX
Total : 1 chip used, 0 gates unused
a
y
From ON Semiconductor LS TTL Data Manual
CS 2204 Spring 2014 Experiment 6 Appendices Page 121
Lab 11
Implementing a Combinational Circuit on a New PCB
Try not
toOR,
use NOT,…
SSI chips
By using TTL LS SSI chips with
AND,
gates
TTL LS SSI Chip Usage ?
a
ab
b
a
ad
d
We need :
Which TTL components ?
2 inverters
5 2-input AND gates
No TTL chip with
1 5-input OR gate
5-input OR gates
z
d
OR
a
ac
c
c
c
cd
d
b
bc
c
2-bit Unsigned
Binary Comparator
From Handout 3
OR
OR
ab + ad + ac + c d + b c
Implement it with 4
2-input OR gates
OR
We need :
2 inverters
5 2-input AND gates
4 2-input OR gates
CS 2204 Spring 2014 Experiment 6 Appendices Page 122
Implementing a Combinational Circuit on a New PCB
Lab 11
Try not
toOR,
use NOT,…
SSI chips
By using TTL LS SSI chips with
AND,
gates
TTL LS SSI Chip Usage ?
a
ab
b
a
Which TTL components ?
ad
d
z
d
a
ac
c
c
c
We need :
2 inverters
5 2-input AND gates
4 2-input OR gates
ab + ad + ac + c d + b c
cd
d
b
bc
c
2-bit Unsigned
Binary Comparator
From Handout 3
1 74LS04 with 6 inverters, 4 inverters unused
2 74LS08 with 4 2-input AND gates, 3 gates unused
1 74LS32 with 4 2-input OR gates, 0 gates unused
Total : 4 chips used, 7 gates unused
CS 2204 Spring 2014 Experiment 6 Appendices Page 123
Implementing a Combinational Circuit on a New PCB
Lab 11
2-bit Unsigned Binary Comparator
Try not to use SSI chips to implement combinational circuits
Use higher density chips : 74LS85 TTL MSI chip : a 4-bit Unsigned
Binary comparator
• We also need a 74LS32 OR-gate SSI chip !
• Two chips used !
a
ab
b
a
ad
d
z
d
a
ac
c
c
c
cd
d
b
bc
c
CS 2204 Spring 2014 Experiment 6 Appendices Page 124
Lab 11
Implementing a Combinational Circuit on a New PCB
2-bit Unsigned Binary Comparator
Try not to use SSI chips to implement combinational circuits
b a 0 0 d c 0 0
0
0
1
74LS85
OR
z
1 74LS85 4-bit Unsigned Comparator
1 74LS32 with 4 2-input OR gates, 3 gates unused
Total : 2 chips used, 3 gates unused
CS 2204 Spring 2014 Experiment 6 Appendices Page 125
Lab 11
Implementing a Combinational Circuit on a New PCB
2-bit Unsigned Binary Comparator
Try not to use SSI chips to implement combinational circuits
b a 0 0 d c 0 0
0
0
1
74LS85
NOT
z
1 74LS85 4-bit Unsigned Comparator
1 74LS06 with 6 inverters, 5 inverters unused
Total : 2 chips used, 5 gates unused
CS 2204 Spring 2014 Experiment 6 Appendices Page 126
Lab 11
Implementing a Sequential Circuit on a New PCB
By using TTL LS SSI chips with
D, J-K,
AND,
NOT,… gates
Try not
to use
SSIOR,
chips
TTL LS SSI Chip Usage ?
y1
x
J
y0
y1
Q
C
K
clock
y2
x
y0
J
x
y0
y0
clock
y2
Least significant FF
x
y2
J
Q
y0
x
y1
y2
K
C
x
y1
Q
C
y2
x
y0
Q
y1
K
x
y2
1 inverter
4 2-input AND gates
6 3-input AND gates
1 4-input AND gate
4 2-input OR gates
2 3-input OR gates
3 positive-edge triggered J-K FFs
Q
y2
clock
Which components ?
y0
We need :
most significant FF
y1
y0
y2
y2
Q
y0
y1
y2
x
x
z
x
CS 2204 Spring 2014 Experiment 6 Appendices Page 127
Implementing a Sequential Circuit on a New PCB
Lab 11
By using TTL LS SSI chips with
D, J-K,
AND,
OR,
NOT,… gates
Try not
to use
SSI
chips
TTL LS SSI Chip Usage ?
Which components ?
There is no positive-edge
triggered J-K FF chip ! We
need one more inverter to
invert the clock
There is no 3-input OR-gate chip !
We implement it with 2-input OR gates
OR
OR
OR
We need :
1 inverter
4 2-input AND gates
6 3-input AND gates
1 4-input AND gate
4 2-input OR gates
2 3-input OR gates
3 positive-edge triggered J-K FFs
We need :
2 inverters
4 2-input AND gates
6 3-input AND gates
1 4-input AND gate
8 2-input OR gates
3 negative-edge triggered J-K FFs
CS 2204 Spring 2014 Experiment 6 Appendices Page 128
Implementing a Sequential Circuit on a New PCB
Try D,
notJ-K,
to AND,
use SSI
By using TTL LS SSI chips with
OR,chips
NOT,… gates
Lab 11
We need :
Here there is no choice !
1 inverter
We have to use SSI chips !
4 2-input AND gates
6 3-input AND gates
But still, try to use a
1 4-input AND gate
4 2-input OR gates
register/counter/shift
2 3-input OR gates
register with a few gates
3 positive-edge triggered J-K FFs
1 74LS04 with 6 inverters, 4 inverters unused
1 74LS08 with 4 2-input AND gates, 0 gates unused
2 74LS11 with 3 3-input AND gates, 0 gates unused
1 74LS21 with 2 4-input AND gates, 1 gate unused
2 74LS32 with 4 2-input OR gates, 0 gates unused
2 74LS112 with 2 negative-edge triggered J-K FFs, 1 FF unused
Total : 9 chips used, 5 gates and 1 FF unused
CS 2204 Spring 2014 Experiment 6 Appendices Page 129
Block 6, Machine Play Block Development
Plays as the machine player
On paper
1.
Lab 9/10
b)
c)
Understand the game rules and how the machine player has to interact
with the rest of the Ppm digital system
Determine the playing strategy (intelligence)
Determine the inputs
Convert the black box view with the inputs determined and the
textual input/output relationship (including the playing strategy) to
an operation diagram
•
•
•
•
3.
How can we implement the block ?
Start with the black box view where the outputs are fixed and the
input/output relationship
a)
2.
Lab 11
Convert the playing strategy to major operations
Partition Block 6 into subblocks
Operation diagram implies the machine player goes through steps taking
several clock periods
The operation diagram also implies that the Block 6 is a tiny digital system
itself
Convert the operation diagram to a high-level state diagram with
microoperations with the same number of states
•
•
A diagram with finite number of states
Distribute microoperations to states
CS 2204 Spring 2014 Experiment 6 Appendices Page 130
Block 6, Machine Play Block Development
On paper
4.
From the high-level state diagram, obtain the datapath
Lab 9/10
•
•
•
5.
6.
Design the sequencer
Start moving the circuits of Block 6 to the computer
Hardwiring or microprogramming
Hardwiring is acceptable if it is not a complex digital system : It is
the case with the Ppm term project
Implement the sequencer which is treated as a state machine
Continue to partition the datapath into subblocks
Design each (sub)block
Implement microperations in datapath hardware
From the high-level state diagram and the datapath, obtain the
low-level state diagram
Decide about how to implement the control unit (sequencer)
7.
Lab 11-13
Lab 11
Copy the termproject folder and paste it as exp6
Start drawing the schematics by using the design on paper
Label the components
CS 2204 Spring 2014 Experiment 6 Appendices
Page 131
Lab 9-10
Block 6, Machine Play Block Development
1.
Lab 11
Start with the black box view where the outputs are fixed and the
input/output relationship
a) Understand the game rules and how the machine player has to
interact with the rest of the Ppm digital system
b) Determine the playing strategy (intelligence)
•
How to determine of the machine player strategy is acceptable ?
At least
3 (three)
different complex conditions
At least
4 (four)
different complex actions
CS 2204 Spring 2014 Experiment 6 Appendices Page 132
Lab 9-10
Block 6, Machine Play Block Development
1.
Lab 11
Start with the black box view where the outputs are fixed and the
input/output relationship
a)
Understand the game rules and how the machine player has to interact with the
rest of the Ppm digital system
b) Determine the playing strategy (intelligence)
•
How to determine of the machine player strategy is acceptable ?
At least 3 (three) different
complex conditions
Player 1 has more points than Player 2 ?
There is an adjacency & RD is not zero ?
Other complex conditions
are possible
There is a position with a 0 & RD is
not zero & next RD not equal to RD ?
Player 1 does not have (64)10 or more points &
the largest regular reward is less than (64)10
Player 1 does not have (64)10 or more points &
there is a position with a zero and RD is not zero
CS 2204 Spring 2014 Experiment 6 Appendices Page 133
Lab 11
Block 6, Machine Play Block Development
1.
Start with the black box view where the outputs are fixed and the
input/output relationship
a)
Understand the game rules and how the machine player has to interact with the
rest of the Ppm digital system
b) Determine the playing strategy (intelligence)
•
How to determine of the machine player strategy is acceptable ?
Lab 9-10
At least 4 (four) different
complex actions
Other complex
actions are possible
Play on the
(rightmost if
equal) largest
regular
reward
position
(directly if
equal)
Play on the
(rightmost if
equal) largest
display
position with
an addition
Play on the
(rightmost if
equal) largest
adjacency
position
(directly if
equal)
Play on
the
(rightmost)
zero
position
directly
Play on the (rightmost
if equal) adjacency
position that results
in the most regular
reward points
(directly if equal)
CS 2204 Spring 2014 Experiment 6 Appendices Page 134
Lab 9-10
Block 6, Machine Play Block Development
1.
Lab 11
Start with the black box view where the outputs are fixed and
the input/output relationship
b) Determine the playing strategy (intelligence)
Non-intelligent machine player strategies
1.
2.
3.
Play in a permanently fixed way : always play on the rightmost position
which does not have a display overflow. If all positions result in display
overflows, skips
Play randomly : when it is time to play, stop a freely running 2-bit counter
and play on that position
Play in a fixed way - round robin fashion : every time it is the turn,
increment a 2-bit counter and play on that position
Do not implement these strategies
CS 2204 Spring 2014 Experiment 6 Appendices Page 135
Lab 9-10
Block 6, Machine Play Block Development
1.
Lab 11
Start with the black box view where the outputs are fixed and the
input/output relationship
b) Determine the playing strategy (intelligence)
•
How to determine of the machine player strategy is acceptable ?
If you do not specify the secondary strategy for
even a single action, it means the machine player
does not work and so you will lose 30 points
CS 2204 Spring 2014 Experiment 6 Appendices Page 136
Lab 9-10
Block 6, Machine Play Block Development
Lab 11
2. Convert the textual input/output relationship (including the
playing strategy) to an operation diagram
Decide about the parallel/sequential implementation issue
Get the subblocks
Convert the playing strategy to major operations
3. Convert the operation diagram to a high-level state diagram
with microoperations with the same number of states
If sequential gather and Sequential compare+decide is decided
A diagram with finite number of states
Distribute microoperations to states
CS 2204 Spring 2014 Experiment 6 Appendices Page 137
Lab 9-10
Block 6, Machine Play Block Development
Lab 11
4. From the high-level state diagram, obtain the datapath
Sequential gather and Sequential compare+decide
Design each (sub)block
Implement microperations in datapath hardware
5. From the high-level state diagram and the datapath, obtain
the low-level state diagram
If Sequential gather and Sequential compare+decide is chosen
6. Decide about how to implement the control unit (sequencer)
Hardwiring or microprogramming ? Choose hardwiring
7. Implement the sequencer which is treated as a state machine
Design the sequencer
Use the 5-state or 9-state counter+decoder combinations given
on previous slides
Make sure the machine player takes
at least 9 clock periods to play
CS 2204 Spring 2014 Experiment 6 Appendices Page 138
Lab 11-13
Block 6, Machine Play Block Development
Lab 11
Move the design to the computer ≡ Implement
Block 6 on computer
Plan where to place the subblocks on the screen
Delete your Block 6 circuits if they are not needed
Start drawing the schematics
First place the components, then their outputs and then their
inputs
Label the components
Save schematic 6, ppm6.sch
CS 2204 Spring 2014 Experiment 6 Appendices Page 139
Lab 11-13
Block 6, Machine Play Block Development
Lab 11
Move the design to the computer ≡ Implement
Block 6 on computer
Start drawing the schematics
Make sure your circuits in Block 6 follow
the Term Project Check List handout
DO NOT IMPLEMENT INFORMATION GATHERING
CIRCUITRY COMBINATIONALLY
USE available circuits in Blocks 1, 2, 3, 4 and 5
CS 2204 Spring 2014 Experiment 6 Appendices Page 140
Lab 11-13
Block 6, Machine Play Block Development
Lab 11
Move the design to the computer ≡ Implement
Block 6 on computer
Start drawing the schematics
Your machine player would not work completely because of
three reasons
It does not follow the game rules
It does not follow your playing strategy
Your playing strategy is not complete
CS 2204 Spring 2014 Experiment 6 Appendices
Page 141
Lab 11-13
Block 6, Machine Play Block Development
Lab 11
Move the design to the computer ≡ Implement
Block 6 on computer
Remember also the following
• Follow all the suggestions and warnings, including the
timetable !
• Follow the 7-step procedure to design Block 6 !
• Start debugging Block 6 starting with the outputs,
proceeding backward
• Make sure everybody has everything related to Block 6
all the time
• Do not have black boxes (macros)
• Only six schematics in the projects
• TAs and I will not answer design related questions !
• Experiment 6 is like an exam : It must be your work !
• No communication with other teams !
CS 2204 Spring 2014 Experiment 6 Appendices Page 142
Lab 11-13
Block 6, Machine Play Block Development
Lab 11
Implementing the machine player, Block 6
Every member of a team must do the schematic design to
remember better for the final exam
The timetable for the rest of the semester
Students will submit the Experiment 6 project which will
include the implementation of
• Block 6
The deadline : 6:50 PM, Friday, May 2, 2014
When it is 6:50 on Friday, May 2, 2014
We will ask students to stop designing the circuits
Then, we will collect the projects
Submit your Experiment 6 during a lab session !
CS 2204 Spring 2014 Experiment 6 Appendices Page 143
Make sure you have the LABS account and see the S drive
Make sure you have installed WebPACK 12.4 on your laptop
Make sure you create a CS2204 folder on both
Read slides at the end to learn about the software, Project Manager,
Schematic design and other related topics
Do not leave the lab before your partners finish
► Help your partners
QUESTIONS ?
Continue
reading the
Term
Project
handout
Digital
Logic
and
State Machine Design
Think about
the machine
player
strategy
CS 2204 Spring 2014 Experiment 6 Appendices Page 144
CS 2204
Lab 12
Digital Logic
and
State Machine Design
Appendices
Labs 9, 10, 11, 12, 13
Experiment 6
?
Spring 2014
Appendices Labs 10 - 12 Outline
Lab 12
Presentation
Machine Player Example 2 (Lab 10)
Digital product development overview (Lab 11)
Component selection for a new chip
• Xilinx component usage
Component selection for a new PCB
• TTL LS SSI chip usage
Semiconductor technology overview (Lab 12)
Submitting the term project
Submitting the term project (Lab 13)
Individual work
Developing Ppm Block 6
CS 2204 Spring 2014 Experiment 6 Appendices Page 146
Lab 12
Silicon Technology Today
a)
Intel Poulson (Itanium)
8 cores,
32 Mbyte L3 Cache
3.1 Billion transistors
170 Watts
b)
c)
d)
e)
f) Today : Multi-chip module,
MCM (>1 die on chip), Giga
Scale, etc.
(200M–3B transistors)
Will there be an end to shrinking the silicon transistor size ?
Silicon transistors are used as switches
CS 2204 Spring 2014 Experiment 6 Appendices Page 147
Digital Hardware Evolution
Lab 12
Switches since 1920s
1) Electromechanical : Relays
2) Electronic switches
i. Vacuum tubes
5cm x 1.5 cm
4cm x 3cm x 1cm
CS 2204 Spring 2014 Experiment 6 Appendices Page 148
Lab 12
Digital Hardware Evolution
Switches since 1920s
2)
Electronic switches
ii.
Discrete transistors
iii.
Integrated circuit transistors : Die contains transistors
1.5 cm x 0.25 cm
Transistor size determined by process length
a)
Small Scale Integration (SSI) (< 64 transistors on chip), 1960s
b)
Medium SI (MSI) (< 2K transistors), 1960s
c)
d)
e)
AND gates (7408), OR gates (7432), NOT gates (7404) chips
Decoder, encoder, multiplexer, counter chips
Large SI (LSI) (< 64K transistors), 1970s
Micro-controller, special-function chips (calculator chips), microprocessor chips
Very Large SI (VLSI) (< 2M transistors), 1980s
Memory, special-function chips, microprocessor chips
Ultra Large SI (ULSI) (> 2M transistors), 1990s
Memory, microprocessor chips, graphics processor chips, networking chips
CS 2204 Spring 2014 Experiment 6 Appendices Page 149
Lab 12
Digital Hardware Evolution
Switches since 1920s
2) Electronic switches
iii. Integrated circuit transistors : Die contains transistors
f) Today : Multi-chip module, MCM (>1 die on chip), Giga Scale, etc.
(200M–2B transistors)
Memory, microprocessor chips
The Intel Phi processor : 6 Billion transistors
AMD Tahiti 7970 GPU : 4.313 Billion transistors
The Intel Dual-core Itanium processor : 1.72 Billion transistors
Intel dual-core Itanium wafer
Intel Dual-Core
Itanium 2 die
AMD Tahiti 7970 GPU
chip
CS 2204 Spring 2014 Experiment 6 Appendices Page 150
Lab 12
Digital Hardware Evolution
f)
Switches since 1920s
Today : Multi-chip module, MCM (>1 die on chip), Giga Scale, etc.
(200M–2B transistors)
The size of transistors depends on the process length
2-input XOR gate
MIPS R10000 die
Process length : 22nm
8 transistors
implement 2
bits on SRAM
memory
A transistor
nano size
AMD Opteron die
Sun Niagara T2 die
IBM Power 6 die
CS 2204 Spring 2014 Experiment 6 Appendices
Page 151
Lab 12
Silicon Technology Today
The Intel Xeon E7 10-core
die with 2.6 Billion
transistors, 32 nm
Intel Xeon E7 wafer
CS 2204 Spring 2014 Experiment 6 Appendices Page 152
Semiconductor Technology Today
Moore’s Law holds since the 1960s :
~5*PL
Lab 12
~3*PL
Every two years the number of transistors on a chip doubles
Transistors become smaller ≡ Process length becomes smaller
• We have been able to reduce the process length
The process is 22nm now
• There are chips with shorter process length now
Samsung 3-D Vertical
NAND
128Gbit Flash EPROM
memory with
45 Billion+ transistors
using 19nm process
Micron 128Gbit Flash memory
die with 64 Billion+ transistors
CS 2204 Spring 2014 Experiment 6 Appendices Page 153
Semiconductor Technology Today
Lab 12
The transistor size depends on process length
Chips with shorter process length later this year
Xilinx Virtex UltraScale, VU 440 : 20nm (20x10-9 meter)
• A 3-D chip : Multiple dice stacked up containing > 20 Billion
transistors
Xilinx Virtex UltraScale : 16nm (16x10-9 meter)
A 3-D chip with 3-D transistors : FinFet transistors !
Xilinx VU 440
CS 2204 Spring 2014 Experiment 6 Appendices Page 154
Semiconductor Technology Today
Lab 12
The transistor size depends on process length
Chips with shorter process length this year
Altere Arria 10 FPGA chip : 20nm (20x10-9 meter)
• A 3-D chip with multiple dice stacked up
Altera Stratix 10 FPGA chip : 14nm (14x10-9 meter)
A chip with 3-D transistors :
Intel FinFet transistors !
CS 2204 Spring 2014 Experiment 6 Appendices Page 155
Lab 12
Semiconductor Technology Today
The transistor size depends on process length
The densest chips
28 nm process
28 nm process
First multi-dimensional chip
Xilinx Virtex-7 2000T FPGA chip
NVIDIA TESLA K40 GPU chip
World’s 2nd densest chip 6.8 Billion transistors
World’s densest chip 7.1 Billion transistors
CS 2204 Spring 2014 Experiment 6 Appendices Page 156
Lab 12
Moore’s Law
An observation made by Gordon Moore holding true since 1965
One of the two founders of Intel
Robert Noyce is the other founder
Number of transistors on a chip doubles every two years
Because transistors are becoming smaller !
We will continue to shrink size of transistors !
We will continue to double the number of transistors
Transistors
are now
nano size
IBM Power 7
8 cores
1.2 Billion
transistors
3-D transistors
increase the transistor
density per chip
3-D chips increase
the transistor
density per chip
CS 2204 Spring 2014 Experiment 6 Appendices Page 157
Silicon Technology and Moore’s Law
Lab 12
Number of transistors on chips doubles every two years
Micron Automata Processor : Processor & memory are one chip !
For high speed search and analysis across massive, complex,
unstructured data
Intel Knights landing microprocessor : 2015 !
72 cores !
Micron Automata Processor die
Intel Knights Landing die
3-D chip with DRAM dice stacked
up on the processor chip
14 nm process
A 3-D chip with 3-D
(FinFet) transistors
CS 2204 Spring 2014 Experiment 6 Appendices Page 158
Silicon Technology and Moore’s Law
Lab 12
Number of transistors on chips doubles every two years
3-D chips ?
Monolithic 3-d chips
• One die but with layers on top of each other
• Many connections between the layers
Die-on-die
• Dice stacked up
• Less number of connections via Through-Silicon Vias (TSVs)
Samsung 3-D Vertical 128Gbit
Flash EPROM with 24 layers
Xilinx Virtex-7 2000T FPGA
IBM’s conception
CS 2204 Spring 2014 Experiment 6 Appendices Page 159
Lab 12
Silicon Technology and Moore’s Law
Number of transistors on chips doubles every two years
3-D chips ?
Hybrid Memory Cube (HMC) !
• Multiple dice stacked up
• There are logic and memory dice stacked up : Hybrid
Micron has 2GByte DRAM chips : 4 stacks of 4 Gbit DRAMs
Micron will have 4GByte DRAM chips this year !
Samsung model
HMC
Hybrid memory Cube
TSVs
TSVs
CS 2204 Spring 2014 Experiment 6 Appendices Page 160
Lab 12
Power Density was Increasing Exponentially !
Power was doubling every 4 years
1000
Rocket
Nozzle
Nuclear Reactor
Watts/cm2
100
Pentium® 4
Hot plate
10
Pentium® Pro
Pentium®
i386
1
1.5m
Pentium® III
Pentium® II
i486
1m
0.7m
0.5m
0.35m
0.25m
0.18m
0.13m
0.1m
0.07m
Process Length
Courtesy : “New Microarchitecture Challenges in the Coming Generations of CMOS Process Technologies” – Fred Pollack,
Intel Corp. Micro32 conference key note - 1999. Courtesy :Avi Mendelson, Intel.
CS 2204 Spring 2014 Experiment 6 Appendices
Page 161
Lab 12
Multi-Core Microprocessors
Since 2005 microprocessor speed increase depends on
Number of operations in the code (the quality of the code)
Number of parallel operations performed
Multi-core microprocessors with reduced frequency consume less
power (generate less heat)
• 2/4/8/16/32/64/128… cores perform operations in parallel
The speed increase continues into the future with more cores on chip
Clock frequency
Number of cores per chip doubles every two years
The memory can become a bottleneck
The memory speed still increases 10% a year
More cores increase the pressure on the memory
The memory wall problem
Multiple cores are not used efficiently
Intel Phi microprocessor
62 cores (2012)
Parallel Programming must improve
• Major concern now
• The parallel Programming wall !
CS 2204 Spring 2014 Experiment 6 Appendices Page 162
Lab 12
Multi-Core Microprocessors
Intel Phi microprocessor (2012) : 62 cores 1 TFLOPS
1997 : Intel supercomputer with 9298 microprocessors (cores)
1 TFLOPS (1 Tera FLOPS)
1 TFLOPS = 1 x 1012 FLOPS
1,000,000,000,000 floating-point operations a second, FLOPS
1,000,000,000,000 real-number calculations a second
Number of cores per chip likely to double every two years
Microprocessor speed is NOT increasing 50% a year any more !
Microprocessor speed is increasing 30% a year
Memory is becoming a bottleneck
• More cores create more pressure on the memory
• The memory speed has been increasing 10% a year
• Memory wall !
Multiple cores are not used efficiently !
• Parallel Programming must improve
• Parallel Programming Wall !
Buses
Bus
Interface
Memory
(DRAMs)
Core
Core
Core
L1, L2, L3
Caches
Core
A multi-core
microprocessor
with 4 cores
CS 2204 Spring 2014 Experiment 6 Appendices Page 163
Next 8-10 Years
More on future projections next week
Lab 12
Double the number of cores every two years
Make sure to handle
errors due to
Alpha particles, neutrons
Defective transistors
Make sure to handle
Power Wall
Memory Wall
Parallel programming Wall
CS 2204 Spring 2014 Experiment 6 Appendices Page 164
Lab 12
Digital Hardware Evolution
Switches since 1920s
2) Electronic switches
b)
c)
d)
NVIDIA Tesla
KEPLER K40
7.1 Billion transistors
300 Watts
e)
f) Today : Multi-chip module, MCM (>1 die on chip), Giga Scale,
etc. (200M–2B transistors)
Will there be an end to shrinking the silicon transistor size ?
CS 2204 Spring 2014 Experiment 6 Appendices Page 165
Next 8-10 Years
Reconfigurable chips ?
FPGA chips
are on Mars !
Lab 12
FPGAs are becoming cost competitive with microprocessors
FPGAs are becoming speed competitive with custom chips
Latest FPGAs also have microprocessor cores to run software as
well
FPGAs are now used for applications where speed and
programmability matter
Xilinx Virtex-II Pro
XC2VP4 FPGA die
From : Wei Wang,
University of Albany
IBM PowerPC 405 core
to run software
Hardware programmable
areas to perform
operations in hardware
CMOS chips
Xilinx Virtex-7 H580T
First 3-D heterogeneous FPGA chip
CS 2204 Spring 2014 Experiment 6 Appendices Page 166
Digital Hardware Evolution
Switches since 1920s
Lab 12
3) Carbon nanotubes
4) Optical switches ?
5) Molecular switches ?
Biological ?
6) ???
The first carbon nanotube computer has been built
Only carbon nanotube transistors used
From : Nature, September 25, 2013
CS 2204 Spring 2014 Experiment 6 Appendices Page 167
Digital Hardware Evolution
Switches since 1920s
Lab 12
3) Carbon nanotubes
4) Optical switches ?
5) Molecular switches ?
Biological ?
6) ???
CS 2204 Spring 2014 Experiment 6 Appendices Page 168
What are we looking for ?
Lab 12
Self-healing, adaptive, self managing,
trustworthy, dependable hardware and software
Efficient parallel processing
Hardware and software reliability
New computational models
New programming languages
So that we have
Many interconnected varying-size computing elements
using each other’s results autonomously
Ubiquitous computing with little human intervention
• Cloud computing to nano computing
Personal agents
Intelligent spaces
• Nano medicine
Smart drugs
Smart diagnosis
CS 2204 Spring 2014 Experiment 6 Appendices Page 169
Digital Hardware Evolution
Switches since 1920s
Lab 12
3) Carbon nanotubes
4) Optical switches ?
5) Molecular switches ?
Biological ?
6) ???
To be continued…
CS 2204 Spring 2014 Experiment 6 Appendices Page 170
Today’s Xilinx Lab Work
Lab 12
Submitting the term project
After drawing the schematics, simulating
circuits separately and testing them on the FPGA
board, make sure that
1) The components are labeled
2) The subsubblocks and the subblocks are separated by
lines and labelled
3) The circuit is beautified
4) The schematic is saved again
5) Functional simulations of the subblocks are done again
6) A Xilinx IMPLEMENTATION is done again
7) Downloading to the FPGA board and testing are done
again
8) Your experiment 6 folder from the S drive is copied to
your laptop
CS 2204 Spring 2014 Experiment 6 Appendices
Page 171
Today’s Xilinx Lab Work
Lab 12
Submitting the term project
After drawing the schematics, simulating
circuits separately and testing them on the FPGA
board
9) Determine whose project will be submitted and then
signal to a TA to submit your project
10) Fill out a Term Project Check List Handout
11) The team project will be copied by the TA
12) Once copied, open the project and download to the
FPGA board to make sure it is copied correctly
13) Print all schematics to prepare for the final exam
14) If you have any files on the local drive, delete them
CS 2204 Spring 2014 Experiment 6 Appendices Page 172
Lab 9-10
Block 6, Machine Play Block Development
1.
Lab 12
Start with the black box view where the outputs are fixed and the
input/output relationship
a) Understand the game rules and how the machine player has to
interact with the rest of the Ppm digital system
b) Determine the playing strategy (intelligence)
•
How to determine of the machine player strategy is acceptable ?
At least
3 (three)
different complex conditions
At least
4 (four)
different complex actions
CS 2204 Spring 2014 Experiment 6 Appendices Page 173
Lab 9-10
Block 6, Machine Play Block Development
1.
Lab 12
Start with the black box view where the outputs are fixed and the
input/output relationship
a)
Understand the game rules and how the machine player has to interact with the
rest of the Ppm digital system
b) Determine the playing strategy (intelligence)
•
How to determine of the machine player strategy is acceptable ?
At least 3 (three) different
complex conditions
Player 1 has more points than Player 2 ?
There is an adjacency & RD is not zero ?
Other complex conditions
are possible
There is a position with a 0 & RD is
not zero & next RD not equal to RD ?
Player 1 does not have (64)10 or more points &
the largest regular reward is less than (64)10
Player 1 does not have (64)10 or more points &
there is a position with a zero and RD is not zero
CS 2204 Spring 2014 Experiment 6 Appendices Page 174
Lab 12
Block 6, Machine Play Block Development
1.
Start with the black box view where the outputs are fixed and the
input/output relationship
a)
Understand the game rules and how the machine player has to interact with the
rest of the Ppm digital system
b) Determine the playing strategy (intelligence)
•
How to determine of the machine player strategy is acceptable ?
Lab 9-10
At least 4 (four) different
complex actions
Other complex
actions are possible
Play on the
(rightmost if
equal) largest
regular
reward
position
(directly if
equal)
Play on the
(rightmost if
equal) largest
display
position with
an addition
Play on the
(rightmost if
equal) largest
adjacency
position
(directly if
equal)
Play on
the
(rightmost)
zero
position
directly
Play on the (rightmost
if equal) adjacency
position that results
in the most regular
reward points
(directly if equal)
CS 2204 Spring 2014 Experiment 6 Appendices Page 175
Lab 9-10
Block 6, Machine Play Block Development
1.
Lab 12
Start with the black box view where the outputs are fixed and
the input/output relationship
b) Determine the playing strategy (intelligence)
Non-intelligent machine player strategies
1.
2.
3.
Play in a permanently fixed way : always play on the rightmost position
which does not have a display overflow. If all positions result in display
overflows, skips
Play randomly : when it is time to play, stop a freely running 2-bit counter
and play on that position
Play in a fixed way - round robin fashion : every time it is the turn,
increment a 2-bit counter and play on that position
Do not implement these strategies
CS 2204 Spring 2014 Experiment 6 Appendices Page 176
Lab 9-10
Block 6, Machine Play Block Development
1.
Lab 12
Start with the black box view where the outputs are fixed and the
input/output relationship
b) Determine the playing strategy (intelligence)
•
How to determine of the machine player strategy is acceptable ?
If you do not specify the secondary strategy for
even a single action, it means the machine player
does not work and so you will lose 30 points
CS 2204 Spring 2014 Experiment 6 Appendices Page 177
Lab 9-10
Block 6, Machine Play Block Development
Lab 12
2. Convert the textual input/output relationship (including the
playing strategy) to an operation diagram
Decide about the parallel/sequential implementation issue
Get the subblocks
Convert the playing strategy to major operations
3. Convert the operation diagram to a high-level state diagram
with microoperations with the same number of states
If sequential gather and Sequential compare+decide is decided
A diagram with finite number of states
Distribute microoperations to states
CS 2204 Spring 2014 Experiment 6 Appendices Page 178
Lab 9-10
Block 6, Machine Play Block Development
Lab 12
4. From the high-level state diagram, obtain the datapath
Sequential gather and Sequential compare+decide
Design each (sub)block
Implement microperations in datapath hardware
5. From the high-level state diagram and the datapath, obtain
the low-level state diagram
If Sequential gather and Sequential compare+decide is chosen
6. Decide about how to implement the control unit (sequencer)
Hardwiring or microprogramming ? Choose hardwiring
7. Implement the sequencer which is treated as a state machine
Design the sequencer
Use the 5-state or 9-state counter+decoder combinations given
on previous slides
Make sure the machine player takes
at least 9 clock periods to play
CS 2204 Spring 2014 Experiment 6 Appendices Page 179
Lab 11-13
Block 6, Machine Play Block Development
Lab 12
Move the design to the computer ≡ Implement
Block 6 on computer
Plan where to place the subblocks on the screen
Delete your Block 6 circuits if they are not needed
Start drawing the schematics
First place the components, then their outputs and then their
inputs
Label the components
Save schematic 6, ppm6.sch
CS 2204 Spring 2014 Experiment 6 Appendices Page 180
Lab 11-13
Block 6, Machine Play Block Development
Lab 12
Move the design to the computer ≡ Implement
Block 6 on computer
Start drawing the schematics
Make sure your circuits in Block 6 follow
the Term Project Check List handout
DO NOT IMPLEMENT INFORMATION GATHERING
CIRCUITRY COMBINATIONALLY
USE available circuits in Blocks 1, 2, 3, 4 and 5
CS 2204 Spring 2014 Experiment 6 Appendices
Page 181
Lab 11-13
Block 6, Machine Play Block Development
Lab 12
Move the design to the computer ≡ Implement
Block 6 on computer
Start drawing the schematics
Your machine player would not work completely because of
three reasons
It does not follow the game rules
It does not follow your playing strategy
Your playing strategy is not complete
CS 2204 Spring 2014 Experiment 6 Appendices Page 182
Lab 11-13
Block 6, Machine Play Block Development
Lab 12
Move the design to the computer ≡ Implement
Block 6 on computer
Remember also the following
• Follow all the suggestions and warnings, including the
timetable !
• Follow the 7-step procedure to design Block 6 !
• Start debugging Block 6 starting with the outputs,
proceeding backward
• Make sure everybody has everything related to Block 6
all the time
• Do not have black boxes (macros)
• Only six schematics in the projects
• TAs and I will not answer design related questions !
• Experiment 6 is like an exam : It must be your work !
• No communication with other teams !
CS 2204 Spring 2014 Experiment 6 Appendices Page 183
Block 6, Machine Play Block Development
Lab 12
Implementing the machine player, Block 6
Every member of a team must do the schematic design to
remember better for the final exam
The timetable for the rest of the semester
Students will submit the Experiment 6 project which will
include the implementation of
• Block 6
The deadline : 6:50 PM, Friday, May 2, 2014
When it is 6:50 on Friday, May 2, 2014
We will ask students to stop designing the circuits
All members of a team except one will log out
The remaining student will close his/her project and wait
Then, we will collect the project from that project
CS 2204 Spring 2014 Experiment 6 Appendices Page 184
Make sure you have the LABS account and see the S drive
Make sure you have installed WebPACK 12.4 on your laptop
Make sure you create a CS2204 folder on both
Read slides at the end to learn about the software, Project Manager,
Schematic design and other related topics
Do not leave the lab before your partners finish
► Help your partners
QUESTIONS ?
Continue
reading the
Term
Project
handout
Digital
Logic
and
State Machine Design
Think about
the machine
player
strategy
CS 2204 Spring 2014 Experiment 6 Appendices Page 185
CS 2204
Lab 13
Digital Logic
and
State Machine Design
Appendices
Labs 9, 10, 11, 12, 13
Experiment 6
?
Spring 2014
Appendices Labs 10 - 12 Outline
Lab 13
Presentation
Machine Player Example 2 (Lab 10)
Digital product development overview (Lab 11)
Component selection for a new chip
• Xilinx component usage
Component selection for a new PCB
• TTL LS SSI chip usage
Semiconductor technology overview (Lab 12)
Submitting the term project
Submitting the term project (Lab 13)
Individual work
Developing Ppm Block 6
CS 2204 Spring 2014 Experiment 6 Appendices Page 187
Block 6, Machine Play Block Development
Lab 13
Implementing the machine player, Block 6
Every member of a team must do the schematic design to
remember better for the final exam
The timetable for the rest of the semester
Students will submit the Experiment 6 project which will
include the implementation of
• Block 6
The deadline : 6:50 PM, Friday, May 2, 2014
When it is 6:50 on Friday, May 2, 2014
We will ask students to stop designing the circuits
All members of a team except one will log out
The remaining student will close his/her project and wait
Then, we will collect the project from that project
CS 2204 Spring 2014 Experiment 6 Appendices Page 188
Lab 11-13
Block 6, Machine Play Block Development
Lab 13
Move the design to the computer ≡ Implement
Block 6 on computer
Start drawing the schematics
Your machine player would not work completely because of
three reasons
It does not follow the game rules
It does not follow your playing strategy
Your playing strategy is not complete
CS 2204 Spring 2014 Experiment 6 Appendices Page 189
Today’s Xilinx Lab Work
Lab 13
Submitting the term project
After drawing the schematics, simulating
circuits separately and testing them on the FPGA
board, make sure that
1) The components are labeled
2) The subsubblocks and the subblocks are separated by
lines and labelled
3) The circuit is beautified
4) The schematic is saved again
5) Functional simulations of the subblocks are done again
6) A Xilinx IMPLEMENTATION is done again
7) Downloading to the FPGA board and testing are done
again
8) Your experiment 6 folder from the S drive is copied to
your laptop
CS 2204 Spring 2014 Experiment 6 Appendices Page 190
Today’s Xilinx Lab Work
Lab 13
Submitting the term project
After drawing the schematics, simulating
circuits separately and testing them on the FPGA
board
9) Determine whose project will be submitted and then
signal to a TA to submit your project
10) Fill out a Term Project Check List Handout
11) The team project will be copied by the TA
12) Once copied, open the project and download to the
FPGA board to make sure it is copied correctly
13) Print all schematics to prepare for the final exam
14) If you have any files on the local drive, delete them
CS 2204 Spring 2014 Experiment 6 Appendices
Page 191
GOOD LUCK ON YOUR EXAMS
HAVE A GOOD SUMMER
Digital
Logic
and
State Machine Design
CS 2204 Spring 2014 Experiment 6 Appendices Page 192