L-3rr-l/CSE Date: 06/04/2023

BANGLADESH UNIVERSITY OF ENGINEERING AND TECHNOLOGY, DHAKA

L-3/T-I B. Sc. Engineering Examinations 2021-2022

Sub: CSE 305 (Computer Architecture)

Full Marks: 210 Time: 3 Hours

The figures in the margin indicate full marks
USE SEPARATE SCRIPTS FOR EACH SECTION
---------- ----_._-, ----- -- ,

SECTION -A
There are FOUR questions in this section. Answer any THREE questions_

I. (a) Complete the provided incomplete diagram of the MIPS single cycle datapath for

the branch if equal (beq) and jump U) instructions. (10)

(b) Consider the following MIPS code: (10)

Iw $tl, O($tO)

Iw $t2, 4($tO)

add $t3, $tl, $t2

sw $t3, 12{$tO)
Iw $t4, SIStO)

add $t5, $tl, $t4

sw $t5, 16($tO)

How many cycles are required to execute the above code? Can you reduce the number
of cycles using code scheduling? If yes, what will be resulting number of cycles?
(c) What do you mean by data hazard for branches? Give MIPS code examples with

explanations for each of the following cases of data hazard for branches: (10)
(i) Needs no stall to resolve
(ii) Needs one cycle stall to resolve
(iii) Needs two cycle stalls to resolve

(d) Consider the following code: (5)

outer:
II some code
mner:
II some code
beq $10, $zero, inner
II some code
beq $t I, $zero, outer
What is the problem with the above code if we use 1 bit branch predictor? How can
you solve that?
Contd P12
 =2=
CSE 305

2. (a) What do you mean by forwarding for data hazard? Design a complete forwarding
unit in the provided diagram with necessary equations for the MIPS pipeline
considering double data hazard. (15)
(b) Draw the block diagram of a dynamically scheduled multiple-issue super-scalar
cpu. (10)
(c) Consider the following program: (10)
Loop: lw $tO, O($sl)
addu $tO, $tO, $s2
sw $10, O($sI)
addi $s I, $s 1, -4
bne $s I, $zero, Loop
Schedule the above program for a dual-issue MIPS with the following configuration:
Two-issue packets, one ALUlbranch instruction, one load/store instruction,
ALUlbranch then load/store.
What will be the Instructions per Cycle (IPC) for this scheduling? Which technique
can increase the IPC even more?

3. (a) Suppose we have a processor with a base CPI of 1.0, assuming all references hit in
the primary cache and a clock rate of 4 GHz. Assume a main memory access time of
200 ns, including all the miss handling. Suppose the miss rate per instruction at the
primary cache is 4%. How much faster will the processor be if we add a second level
cache that has a IOns access time for either a hit or a miss and is large enough to
reduce the miss rate to main memory to I%? How much faster will the processor be if
we add a third level cache that has a 40 ns access time for either a hit or a miss and is
large enough to reduce the miss rate to main memory to 0.5%? (10)
(b) Explain with necessary diagrams how the page table works with respect to the
virtual address, physical address, main memory, and disk. (10)
(c) You are given the following hit/miss status ofTLB, Page Table and Cache. (10)
Serial No. TLB Page Table Cache
I Hit Hit Hit
2 Hit Miss Hit
3 Miss Miss Hit
4 Miss Miss Miss
5 Miss Hit Hit

Table 3(c)
Explain which of the scenarios in Table 3(c) is possible or impossible and under what
circumstance with proper reasoning.
(d) Explain how snooping protocol solves the cache coherence problem with an

example. (5)
Contd P/3
 =3=
CSE 305

4. (a) Assume there are three small caches, each consisting of four one-word blocks and
uses LRU replacement policy. One cache is fully associative, a second is two-way set-
associative, and the third is direct-mapped. Find the number of misses for each cache

organization given the following sequence of block addresses: (15)

1,3,2,4,5,1,3, 1,3,5,3,2
(b) Show with block diagrams how contemporary PCs with Intel and AMD CPUs

connect a separate GPU. How do the CPU and GPU access each other's memory? (10)
(c) What do you mean by kernel, grid, and thread block of the CUDA paradigm?
Briefly describe how they map to the streaming processor (SP) cores and streaming

multiprocessors (SM) of the unified GPU architecture ofNVIDIA. (10)

SECTION - B
There are FOUR questions in this section. Answer any THREE questions.

5. (a) The following four design principles have been guiding the instruction-set
designers to find a balance between the number of instructions needed to execute a
program, the number of clock cycles needed by an instruction, and the speed of the

clock. (3 x5= 15)

(i) Simplicity favors regularity
(ii) Smaller is faster
(iii) Good design demands good compromise
(vi) Make the common case faster
You are given several design features of MIPS instruction-set architecture in the
following. Now, please identify which of the above principle(s) is behind each of these
design decisions.
(i) Keeping conditional branch's offset value in a range of 16 bits.
(ii) Keeping 32 registers rather than many more.
(iii) Consistent instruction format, i.e., always requiring three registers for R-
type Instructions.
(iv) Multiple instruction formats to allow flexibility.
(v) Reduced instruction set, Complex instructions (i.e., pseudo instructions
like bgt, bge, mov etc.) are translated into one or more basic instructions.
(b) Assume that 2% of the runtime of a program is not parallelizable. This program
runs on 24 cores of an Intel Xeon Gold processor. Under the assumption that the
program runs at the same speed on all of those cores and there are no additional
overheads, (4+6=10)
Contd P/4
 =4=
CSE 305
Contd .... for Q. No. Sib)

(i) What is the parallel speedup for 24 cores?

(ii) Is it possible to make the program 60 times faster? If yes, how can that be
achieved? If not, mention the reasons.
(c) Discuss how can subword parallelism be used to accelerate common operations,

such as matrix multiplication or image processing? (10)

6. (a) Write the MIPS assembly code for the C code shown in the following figure
(Figure: 6.a). (15)

int fib (int n) {

if (n==O) return 0;

else if (n == 1) return 1;

else return fib(n-l) + fib(n-2);

Figure: 6.a
(b) Suppose the program counter (PC) is set to Ox2000 0000. Explain your answer for

the following questions. (5+5= 10)

(i) Is it possible to use the jump Ul MIPS assembly instruction to set the PC
to the address Ox4000 OOOO?
(ii) Is it possible to use single branch (beq/bneq) instruction to set the PC to
this same address?
(c) Draw the block diagram of 32-bit combined multiplication and division hardware
which uses 32-bit ALU, and briefly mention functions of different components of this

hardware. (10)

7. (a) Assume that you have four different threads as shown in figure (Figure: 7.a) below.
Show how the four threads could be combined to execute on the processor more
efficiency using the following three multithreading options. You only need to show the

first 12 timeslots for each of the following options. (5+5+5=15)

(i) A superscalar with coarse-grained multithreading

(ii) A superscalar with fine-grained multithreading
(iii) A superscalar with simultaneous multithreading
Contd PIS
 =5=
CSE 305
Contd .... for O. No. 7(a)

Time Thread A Thread B Thread C Thread D

T1 A A B B B C C C D

T2 A C C C C D D

T3 A A A A D D D

T4

T5 C C C D D D D
T6 A D D

T7 A A B B B B C C C C D
T8 A A A B B D D D

Figure: 7.a
(b) Suppose you are using Floating Point Operations Per Second (FLOPS) as a
performance metric for comparing processors. Your research partner believes that
FLOPS might be a misleading metric for measuring the general performance of a
processor, but it could still be a useful performance measure for a specific part of the
processor or a specific type of processors. Do you agree or disagree with your research
partner's statements? Provide a detailed explanation to support your position. (10)
(c) With illustrative example(s), explain how vector processor differs from array
processor. (10)

8. (a) Consider two different implementations (PI and P2) of the same instruction set
architecture. There are three classes of instructions A, B, and C. Suppose, a program
has 200,000 instructions divided into three classes as 25% class A, 60% class B, and
15% class C. The clock rate and CPl of each implementation are given in the following
table (Table: 8.a). (3+3+5=11)
Clock CPlof CPlof CPlof
Implementation
Rate Class A Class B Class C
PI 2.7 GHz 3 3 2
P2 3.5 GHz 2 4 1
Table: 8.a
(i) Find the total clock cycle required in both implementations.
(ii) Calculate the execution time required for both implementations and
determine which implementation is faster.
(iii) How much must we improve the CPI of Class C instructions if we want
the program to run two times faster in the better implementation
determined in the previous question?
(b) Consider representing the set of consecutive positive integers {l, 2, 3, 4, ..., n}
using IEEE single precision floating point (8-bit exponent and 23-bit mantissa). Find
the largest n such that every number in the above set can be represented. (14)
(c) What are the different addressing modes of MIPS? Illustrate the calculation process

for each addressing mode. (10)

 RegDst
Branch
MemRead
.,
In
~
-0 on
Instruction [31-26],
Control
MemtoReg
~ Oil' ALUO
c: II
~
~
'"
:;
'"
-<
-2
to
0
~
MemWrite
ALUSrc
ReaWrite
(J'I
II

.,
0
c:
~ to
:J '"~
0" Instruction [25-21]
'":; Read
to ...
:J
Read register 1 Read
~
'"q
ii'
~
~
PC 1*-1 address
II Instruction [20-16] Read
register 2
data 1

Instruction 0
[31--0] M Write Read
u register data 2
Instruction Instruction [15-11] 1X
memory
1111
Write
data Registers \.!.../
I I I Write
' memory
Data
data

Instruction [15-0] 16

Instruction [5--0]

,
 IFIID lDIEX EXIMEM MEWM3

V>
~ jj r- Read
•• S register 1 Read

i> ."
"0

••
w data 1

,. c
~
-c
Read

-
Instruetlon register 2
••• ""V
~. 0- memory t- Registers Read
Address
Read
or ~ Wnte data 2 data
-< regIster II
0 Q O.la
c c
~ r-
Write memory -V
•• •••!:!.
:J '" 0
data
~ 11
'":E :J Write
N
•••
~
'"n
"'.
~
E 16 032 data
 .,

L-3ff-I/CSE Date: 07/05/2023

BANGLADESH UNIVERSITY OF ENGINEERING AND TECHNOLOGY, DHAKA
L-3/T - I B. Sc. Engineering Examinations 2021-2022

Sub: CSE 307 (Software Engineering)

Full Marks: 210 Time: 3 Hours

USE SEPARATE SCRIPTS FOR EACH SECTION
The figures in the margin indicate full marks
.~ -----_._-------~-----_.~--- -----_._----_._-----

SECTION-A
There are FOUR questions in this section. Answer any THREE questions.

1. (a) Differentiate the use cases of these following design patterns with necessary

examples and/or figures: (16)

Factory Method Pattern, Abstract Factory Pattern,

Builder Pattern and Bridge Pattern

(b) Your younger brother who wanted to build an Avengers themed game. For his game
he wrote a method which takes a Super Hero's name as input and returns the Super

Hero item used by that Super Hero. He wrote the method as follows: (13)
class GetSuperHeroltem {
public SuperHero Item suit;

public SuperHero Item hammer;

public SuperHero Item shield;

public SuperHero Item arrow;

public SuperHero Item getltem(String heroName) {

if (heroName.equalslgnoreCase("lronMan"» {
return suit;

}
else if (heroName.equalslgnoreCase("Thor"» {
return hammer;

}
else if (heroName.equalslgnoreCase("CaptainAmerica"» {
return shield;

}
else if (heroName.equalsignoreCase("Hawkeye"» {
return arrow;

}
else {

return null ;

}
}
Contd P/2
 =2=
CSE 307
Contd ... Q. No. l(b)

You came to know about his little project and saw this piece of code. You know a
better way to implement the functionality he wanted. Now, re-write the code above in
such a way that would be much easier to read and maintain, also your method should
have constant run-time (amortized).
(c) Discuss briefly the following System Implementation methods. Also, state a real-

world use case for each of the implementation methods: (6)

Parallel implementation. Plunge implementation.
Pilot implementation and Phased implementation.

2. (a) Let's assume you are building your own computer networking model. Your model
has five (5) layers. Such as: Physical Layer, Data-link Layer, Network Layer, Transport
Layer and Application Layer. When an user wants to send a message (e.g. "hello")

using your designed model, it works like this: (20)

• First user creates a Packet Object. Packet object has two properties: J'vfessage and
Length. If user wants to send the message "hello", the Packet object would look like
this:
message: hello, length: 5
• Then the Packet object is received by the Application layer. Application Layer adds a
header to the original Packet object. Packet object would look like this:
message: APPHEADER_hello, length: 15
• Then the Packet object is received by the Transport layer. Transp0l1 Layer adds a
header to the received Packet object. Packet object would look like this.
message: TRHEADER_APPHEADER_hello, length: 24
• Then the Packet object is received by the Network layer. Network Layer adds a
header to the received Packet object. Packet object would look like this.
message: NETHEADER _ TRHEADER _AP PHEADER_hello, length: 34
• Then the Packet object is received by the Data-link layer. Data-link Layer adds a
header and a trailer to the received Packet object. Packet object would look like this.
message: DHEADER _NETHEADER _ TRHEADER_AP PHEADER_hello _ DTRAILER.
length: 51
• Then the Packet object is received by the Physical layer. Physical Layer adds a
header to the received Packet object. Packet object would look like this.
message:
PHEA DER_DHEADER _NETHEADER _ TRHEADER _AP PHEADER_hello _D TRAILER.
length: 59
And retums this as the tlnal Packet object.
Contd P/3
 =3=
CSE 307
Contd ... Q. No. 2(a)

Identify the design pattern that can best capture the scenario above and implement it
using your preferred language (you can use pseudo syntax). You must provide the
UML class diagram of your implementation.

(b) Consider the following simplified description of a university: (10)

A university has multiple departments. Each department can have a number of
faculties. A department must have one department head. Courses are offered by the
departments. The departments have the fit/I freedom to not to offer any course. Students
are also a member of the university. Students aI/end coursers) which is instructed by
the faculties.
Draw a class diagram for this university. Add attributes and methods when necessary.
Visibility modifiers (public, private, etc.) are not required.
(c) Briet1y describe the differences between Functional and Non-Functional

requirements. (5)

3. (a) Suppose you are working on a restaurant's software development team. Your
restaurant provides four kinds of set menus such as: Veggie Harvest, Chicken Delight,
Beef Fiesta, Sea Shanty. Veggie Harvest contains Mushroom Rice, Paneer Masala and
Fried Vegetable Pakora. Chicken Delight contains Chicken Fried Rice, Butter Chicken
and Fried Chicken wings. Beef Fiesta contains Beef Fried Rice, Beef Chili Onion and
Fried Beef Bacon. Sea Shanty contains Rice with Shrimp, Crab Masala and Fried

Calamari. (20)
Your restaurant have three different kitchens named as Rice Station where all the rice
based items are prepared, lv/ain Mania where all the main dishes (Panner Masala,
Butter Chicken, Beef Chili Onion and Crab Masala) are prepared and Fry More where
the fried items are prepared.
Your restaurant takes orders from the user. then assembles the items prepared by the
kitchens described above and delivers it.
Your job is to identify the design pattern that can best capture the scenario above and
implement it using your preferred language (you can use pseudo syntax). You must
provide the UML class diagram of your implementation. "'Be careful, as users are
very sensitive to their orders.'"
(b) Briet1y discuss the six (6) types of testing methods as follows: Unit testing,
Integration testing, Nan-Functional testing, Regression testing, Acceptance testing and

Beta testing. (10)

(c) "It incurs less cost to fix a bug, if we found the bug in the later stages of SDLC" -

Do you agree with this statement? Justify your answer. (5)

Contd P/4
 =4=
CSE 307

4. (a) For each of the situations below, identify the most specific pattern used in that
situation. You need to write the pattern name with sufficient justification (UML class

diagram if necessary). (20)

(i) You are building your own video steaming platform named NlieiFlix. In the
earlier version of NlieiFlix, it only provides three types of genres: Horror, Thriller
and Comedy. A user can choose anyone or more of these genres as their preferred
genre. When a movie releases you must recommend the movie to the users who are
interested in that particular genre (in which the newly released movie belongs).
(ii) You want to build your own version control system namedjil. Where you want
to provide some basic functionalities such as:
kommit that saves your current updates locally but doesn't sync with the remote
version, pllssh that syncs all the "kommit"ed codes with the remote version and
slashh that discards all the un"pussh"ed "kommit"s and retrieves the latest remote
version to the local.
(iii) You work in a telecommunication company named BanglaPhone.
BanglaPhone have two different implementations for their mobile communication.
One of the implementation is more stable, can support a lot of users but it incurs
more cost and tends to be slower. The other implementation is fast, cheaper but less
stable if user count surpasses a threshold. Your company wants you to switch
between the implementations without hampering any other code segments based on
the current number of user under a specific cell tower.
(iv) You work on a software development team of a peer-reviewed journal named
R2-D2. A peer-reviewed journal works like this: Authors submit their article in the
journal. A team of expert receives a number of such articles and express their
opinIOn (known as reviews). These reviews are acknowledged by the authors.
Authors try to update their article to address the reviews, and re-submit their article.
Finally, those experts receive the modified version of those articles and they decide
to accept or reject the article. In all of these communication no author could know
the identity of the reviewers and vise-versa. These communication occurs via an
internal team formed by the journal committee. You need to build an automated
system to facilitate this situation.
(b) "The software should provide update notification after a fixed time. Users should be
able to perform action based on the notification" - assess the quality of this requirement

statement based on the different quality measures. (10)

(c) Describe with example five (5) negative testing ideas that you will use to test a web

application. (5)

Contd PIS
 =5=
CSE 307

SECTION - B
There are FOUR questions in this section. Answer any THREE.

5. (a) Describe, with an appropriate example, the uncertainty and loss associated with a

particular risk in a typical software project. (10)

(b) Give an overview of the different steps involved in a sprint in scrum method of

software development. (20)

(c) Discuss the necessary of writing short. useful, and up-to-date code documents. (5)

6. (a) Point out how incremental and evolutionwy process models address the

shortcomings of waterfall process model in a software project. (10)

(b) Imagine that you are project manager organizing and leading different projects in a
software company. Some information on one such project, which has been running for

the past one month, is provided below in Table for Question 6(b). (15)
Objective Total PV PV after One Month EV after One Month
A $70 $50 $40
B $40 $40 $35

C $30 $20 $30

D $60 $35 $35

E $50 $0 $0
Table for Question 6(b)
Here, PV and EV stand for planned value and earned value, respectively. The company
expended $130 in this project during the past month. Now, given the information,
compute schedule performance index (SPl), cost peljormance index (CPl), and
estimated cost at completion (EA C) of this project after one month. Put some remarks
on the progress of this project based on the obtained values.
(c) Deline code smell in your own words. Provide 3 (three) examples of smell in a

program which may degrade the quality of the code. (10)

7. (a) State the reasons behind recent shift from adopting traditional process models to

adopting agile process models in software projects. (10)

(b) Suppose that you have been assigned to analyze the schedule of the software
project, in which you are currently working, by your project manager. Consider the

following information about this project in Table for Question 7(b). (20)

Contd P/6
 =6=
CSE 307
Contd ... Q. No. 7(b)

Task Predecessor(s) Duration (in Week)

A - 3
B A 1.5
C A 2
D - 3.5
E D 4
F C,E 2.5
G B 1
H C, F,G 0.5
Table for Question 7(b)
Now, determine strict deadline. slack of different tasks, and critical path of this project
by applying critical path method (epM).
(c) "Adding manpower to a late software project makes it later." - justify this

statement. (5)

8. (a) Discuss the role of driver and navigator in the content of code review in pair

programming. (10)
(b) "Kanban method focuses on the visualization aspect of a software project with

kanban cards and kanban board. " -elaborate on this statement. (15)
(c) Explain, in your own words, the people and the process components of a typical

software project. (10)

'l'

L-3rr-l/CSE Date: 30/0312023

BANGLADESH UNIVERSITY OF ENGINEERING AND TECHNOLOGY. DHAKA
L-3/T-I B. Sc. Engineering Examinations 2021-2022

Sub: CSE 309 (Compiler)

Full Marks: 210 Time: 3 Hours
The figures in the margin indicate full marks
USE SEPARATE SCRIPTS FOR EACH SECTION

SECTION-A
There are FOUR questions in this section. Answer Q. NO.1 and any TWO from the rest.
Question NO.1 is COMPULSORY.

1. (a) Consider the C code shown below contained in two separate files. Discuss in detail
the issues faced by the linker and the loader when he program is compiled and then
executed. How will these issues be resolved? Explain. (13)

main.c

I #inc1ude <stdio.h>

2 void main ()

3 (

4 ••••••• ;

5 int i;

6 i = subfunction();

7 exitO;

8 }

subcode.c

I void subfunetion()

3 int it n = 0;

4 for (i'= 1; i <= 50; i++)

6 n = n + i;

8 return nj

9 }

(b) The partial contents of a buffer in lexical analyzer is dhaka_+++_123. 456_,

where _ indicates a space. At the current moment, both the lexemeBegin and

forward pointers are on d at left. From the perspective of the C programming

language, describe clearly the pointer movements and recognition of tokens that will
happen. (10)
Contd P/2
 =2=
CSE 309
Contd .... for O. No.1

(c) Justify with proper reasons the acceptability (or unacceptability) of the each of the

following statements at any valid state in shift-reduce parsing. (12)

(i) Viable prefixes appear only at the bottom of the stack and not inside.
(ii) Viable prefixes appear only at the top of the stack and not inside.
(iii) The stack contains only a set of viable prefixes.
(iv) Viable prefixes do not continue past the right end of the rightmost handle
of that sentential form.

2. (a) Among the reasons why the analysis portion of the compiler is normally separated
into lexical analysis and parsing (syntax analysis) phases, simplicity of design is the

most important consideration - explain and justifY. (to)

(b) In the LR-parsing algorithm, if ACTION [sm.G;] = reduce A ~ p, describe in detail

how exactly this action is carried out. The symbols have got their meaning used in the

class. What is the relationship of f3 with the stack content? (10)

(c) Enumerate and explain the classes that cover most or all of the tokens In the

programming languages. (7)

(d) What is the one-liner rule to determine whether a token will require an attribute or

not? Are all the token attributes single values? Explain. (5)

(e) Is input butTering essential in lexical analysis? Explain. (3)

3 (a) Explain clearly with examples, for a production rule like, X ~ l;Y, ...Y" when E is

included in FIRST(X). (8)

(b) Describe what exactly happens during parsing when a cell of the predictive parsing

table has an empty production rule like, A ~ E. (6)

(c) What are the key decisions during top-down and bottom-up parsing? (6)

(d) Consider the following grammar: (10)

A~kXYz
X~Xwrlw
Y~g

For the string kwwrgz, draw the parse tree and hence identify the handles for bottom-

up parsing.
(e) In shift-reduce parsing, the handle will always eventually appear on top of the

stack, never inside - justify this statement for the problem in (d). (5)

Contd P/3
 =3=
CSE 309

4. (a) Eliminate left recursion from the grammar: (12)

S -> SBria
B -> Cslb
C ->Sf Ic
(b) For the grammar shown below, lind the LR(I) canonical items. (10)
S -> aAd I bBd I aBe I bAe
A ->c
B->c
(c) From the LR(I) canonical items in Question 4(b) construct the CLR parsing table. (8)
(d) Comment on the similarity and dissimilarity between the sequences of shifts and

reductions for the LR and LALR parsers. (5)

SECTION -B
There are FOUR questions in this section. Answer any THREE questions.
All the symbols have their usual meanings in the context of compilers
unless explicitly mentioned.

5. (a) What is a dependency graph in the context of Syntax-Directed Definition (SSD)?

How is a dependency graph constructed? What is the application of a dependency

graph? ( 4+4+ 3= 11)

(b) The following Syntax-Directed Translation Scheme (SDT) computes the value of a

string of O's and I's interpreted as a positive, binary integer. (10)

B -> B,O {B.val = 2x B,.val}
IB,I {B.val=2xB,.val+l}
II {B.val=l}
Rewrite this SDT so that the underlying grammar is not left recursive, and yet the same
value of B.val is computed for the entire input string.
(c) Give an example of an L-attributed SOD on an LR grammar. Is it possible to
handle every LR grammar and L-attributed SOD bottom up? Give an intuitive
argument in support of your answer. (6+8=14)

6. (a) Illustrate two distinctive aspects that distinguish Static Single-Assignment (SSA)
from three-address code. How does SSA facilitate code optimization? Explain with an

example. (8+5=13)
(b) Consider the following SOD for generating three-address codes using the fall-

through technique. (14)

Contd P/4
 =4=
CSE 309
Contd .... for Q. No. 6{b)

Production Semantic Rules

S ~ if (B) S, B. true - fall

B.fafse = Sf. next = S.next

S.code = B.code II S,.code

B ~ Bf II B, B,.true = if B.true t- fall then B.true else newLabe/O

Bf.false = fall
B,. true = B. true

B,.false = B.false
B.code = if B.true t- fall then Bf.code II B,.code
else B,.code II B,.code II/abel(Bf.true)

Now add rules to the SOD above for the following two productions using the same
fall-through technique.
(i) B ~ B, & & B,
(ii) B ~ £, rei £,
Assume all the symbols, attributes, functions, labels, and notations have their usual
meamngs.
(c) Write down a translation scheme for generating code using backpalching for the
flow-of-control statement yielded by the following production. You may add marker
symbols in the production as required; specify the semantic actions corresponding to
the marker symbols. Make any other justified assumptions, as necessary. (8)
S ~ for(S,;B;S,)SJ

7. (a) Which condition must procedure calls or aClivalions of procedure satisfy to enable
stack allocation? Explain. Give an example of a programming language feature that
violates the condition and thus cannot be implemented with purely a runtime stack.
What are calling and return sequences in the context of procedure calls? (6+6+5= 17)
(b) Consider the network of objects in the figure below. Assume, X denotes the rool
sel. Suppose at some point in time, the pointer A ~ C is deleted. Then we execute
Cheney's copying garbage collection algorithm on the network. Also, suppose that, (18)
(i) Each object has size 100 bytes,
(ii) The unscanned list is managed as a queue, and when an object has more
than one pointer, the reached objects are added to the queue in
alphabetical order,
(iii) The From semispace starts at location 0, and the To semispace starts at
location 10,000, and
(iv) Initially, all the objects in the heap are arranged m alphabetical order
starting at byte O.
What is the value of NewLoclion(o) for each object 0 that remaInS after garbage
collection? Draw the heaps before and after running garbage collection, showing-
(i) locations of the allocated objects, (ii) references running among the objects. What is
the time complexity of the algorithm?
Contd """"" PIS
 =5=
CSE 309
Coutd .... for Q. No. 7(b)

Figure for Question 7(b)

8. (a) Optimize the following three-address code by eliminating common subexpressions,

performing reduction in strength on induction variables, and eliminating all the
induction variables as possible. (10)

dp = 0
j=O
L: t1 = j.a
12 = A[t1)
t3 = j.a
. t4 = B[t3]
t5 = 12.t4
dp = dp + t5
i= j + 1
if j<n goto L

(b) Given the flow graph of a program, formulate the problem of global register
allocation as a graph coloring problem. Show detailed formulation steps using the tlow
graph in the figure below as an example. Subsequently, find a register allocation for
the given program using Chaitin's algorithm. Assume that three physical registers are
available. Illustrate all steps of the algorithm. (13+ 12=25)

a=b+c
d=d-b 61
e=a+f

63

64

b, e live

Figure for Question alb)

L-3!f-l/CSE Date: 02/05/2023
BANGLADESH UNIVERSITY OF ENGINEERING AND TECHNOLOGY, DHAKA
L-3/T -I B. Sc. Engineering Examinations 2021-2022

Sub: CSE 311 (Data Communication)

Full Marks: 210 Time: 3 Hours

USE SEPARATE SCRIPTS FOR EACH SECTION
The figures in the margin indicate full marks
---_._------- ----------_ .•._--------_._---------------_ _ _--_ .•----------
.•. ..

SECTION-A
There are FOUR questions in this section. Answer any THREE questions.

1. (a) Derive the Fourier spectmm of a gate signal of width B. Also, find the exponential
Fourier series of a periodic gate signal of the same width and period 2B. Draw all four
time domain and spectral domain representations. Comment on and correlate your

lindings in the spectral representations. (20)

(b) TI carrier system multiplexes 24 voice signals to product Digital Signal Level
(DS 1) which is then transmitted. How are these individual signals separated at the

receiving end? (15)

2. (a) Differentiate between all-pass and distortionless transmission systems. Draw the
frequency response of a distortion less transmission system. Justify from its time

domain representation why it is unrealizable. (20)

(b) Draw the graphs of the NRZ-I and 2BIQ schemes for the following two data

streams. Assume that the last signal level has been positive. (15)
Data streams: 0110011001100110 and 1100110011001100

3. (a) With appropriate examples and mathematical derivations, establish the relationship
between time compression and frequency compression of a signal. Nonlinear
quantization uses logarithmic compression of a signal, yet it does not change the

bandwidth of the signal. Why is it so? Why is nonlinear quantization necessary? (20)
(b) While sampling a signal g(t) band limited to B at Nyquist sampling rate, all samples
are found to be zero except at time t = 0, where it is A. Derive the most simplified
cxpression of the signal g(t) from its sample values. Justify and correlate the expression

you derived and the sample values you used. (15)

Contd P/2
 =2=
CSE 311

4. (a) In a video surveillance system, data from 24 video cameras are brought to a
processing center and are sampled, quantized, binary coded and time-division
multiplexed. The multiplexed data are then transmitted to a monitoring system over a
cable. Assume the bandwidth of all video signals is 200 Hz. The maximum acceptable
error in sample amplitudes is 0.25% of the peak signal amplitude. The sampling rate is
exactly the Nyquist rate. Derive the minimum cable bandwidth needed to transmit
these data. (18)
(b) "Delta modulation is a special case of differential pulse coded modulation.
However, they differ on what types of signals they can process, e.g., continuous time
and discrete time signals." Justify the statement with appropriate mathematical
derivations and block diagrams of both modulation techniques. (17)

SECTION -B
There are FOUR questions in this section. Answer any THREE questions.

5.

.l /31.~
./
~
Ml~)
M~)
m(l)
lOW Pass
Aler
?

mz{l)

'j
Cz{l)
SwI1ch.
52 Mz{l)

F1••••.• : 5.1

Consider the circuit diagram shown in figure 5.1 and assume the corresponding signals
to be as following.
ml(l) = IOcos600t, m2(1) = IOcos900t, CI(t) = 20cos30000t, C2(t) = 20cos60000t Now
Answer the following questions.
(a) Assume that, both the switches are on (circuit connected). Draw the frequency
spectrum of Inl(t) and m2(t). Determine the mathematical equations of MI(t), M2(t),
M(t) and met). Draw the frequency spectrum of each of them too. (20)
(b) Considering both switches being on, explain how it is possible to generate ml(t) as the
output of the demodulation side. [You can use the derived equation ofm(t) from 5(a)] (5)
(c) Assume that, the switch, SI is open and the carrier, C2(t) is also passed with M2(t).
Draw the envelope of M(t). Can this scheme be considered as a tone modulation now?
Find out the modulation index, power efficiency under this constraint. (10)

Contd P/3
 l
=3=

CSE 311

6. (a) What is power spectral density? Briefly explain how a signal power is detemlined

given its power spectral density. (5)

(b) What is Quadrature Amplitude Modulation (QAM)? Explain how the modulation
and the demodulation schemes of a QAM signal work, including their circuit diagrams.
Describe how the above-mentioned modulation-demodulation scheme can be extended

to create a Quadrature Phase Shift Keying (QPSK) signal. (13)

(c) Draw the constellation diagram of the generic QPSK signal created by the scheme
in 6(b). Consider the data stream: "10010 II0". Assume this data is passed using thc
QPSK signal above. Draw the bipolar NRZ fonn graph representing the Q-channel of
the data stream. Mention the corresponding phase shift in the QPSK signal for each
pair of clock cycles. Determine two timestamps with the lowest and the highest phase

shift during transmission. (9)

(d) How does Offset-QPSK (OQPSK) benefit the phase shifting scenario of the QPSK
scheme? For the same data stream of 6(c), how will you create a 16-ary PSK signal

using the previous QPSK signal? What will be the minimum phase shift then? (8)

7. (a) A modulating signal is defined using the function: met) = 3t - 6Lo.5f J Volts, where

J
Lf is the integer part of 1. Draw the modulating signal and determine its frequency in
Hertz. The carrier signal is defined to be c(t) = cos (21lfct), fc = 10kHzVolts. Write the
equation of a Phase Modulated (PM) signal, (where c(t) is modulated by met»~. Draw
the graphs of the catTier signal and the PM signal Briefly explain the nature of phase

shifting in your graph with respect to met). (16)

(b) The equation of an FM signal is m'(t) = 20cos(5x I07t+4sin(7x IOJI)) volts.
Determine the carrier and modulating frequencies, modulation index, and frequency
deviation.

If the frequency sensitivity is 2 HzIV olt, determine the modulating signal. (13)
Assume,

I jo =
-0.025 x mr.h = -0.0175 x mr'jz = 0.09 x mr.h = 0.1075 x mr.j• = -0.07 x
mr.h = 0.0325 x mr.j6 = 0.0125 x m{.js = 0.0325 x mr.h = 0.005 x mr.j" = 0.0. n >7

Calculate the total power of the transmitted signal.

(c) Discuss three differences between Amplitude Modulation and Angular Modulation. (6)

Contd P/4
 =4=

CSE 311

8. (a) Show the significance of Hilbert transformation in achieving a Single Sideband

Modulation. Explain using figures of frequency spectrum and mathematical analysis. (13)
(b) You are assigned to arrange a pattern of lighting in a family get-together using 2

LEDs. The pattern should be as following: (8)

During a period of 800 ms, the 1st LED will be lit for the first 200 ms, the 2nd one will
be lit for the next 400 ms, and the Istone will be lit again for the last 200ms.
All you are provided with are: a sinusoidal signal,s(t) = cos21t x 1.25t Volts and two
Op-Amps. Explain how you are going to avail the desired functionality using circuit
diagrams for the 2 LEDs. Assume, to keep the LED lit, you have a 5 Volts dc supply.
(c) What is Frequency Division Multiplexing (FDM)? Explain the benefit of FDM in

handling various range of frequencies for a large range of communication channels. (7)
(d) Show that, the minimum frequency difference to make two signals orthogonal is,
I
81'= - (7)
2Th
L-3ff-l/CSE Date: 13/04/2023
BANGLADESH UNIVERSITY OF ENGINEERING AND TECHNOLOGY, DHAKA
~~,. L-3/T-I B. Sc. Engineering Examinations 2021-2022
(
Sub: CSE 315 (Microprocessors, Microcontrollers, and Embedded Systems)

Full Marks: 210 Time: 3 Hours

USE SEPARATE SCRIPTS FOR EACH SECTION
The figures in the margin indicate full marks

SECTION-A
There are FOUR questions in this section. Answer any THREE questions .
• Assume system clock frequency IMHz if not given .
• List of registers and necessary diagrams are at the end of the question .
• If configuration for any required register/control-word/bit is missing, just assume a
configuration and clearly show the assumed configuration.

I. (a) Suppose an active-high push switch is connected to the PD3 pin of an ATmege32.
Also, eight LEOs are connected to PBO-PB7. Write a C code for an 8-bit ring counter
using an interrupt. An 8-bit ring counter counts like 00000001, 000000010, 00000100,
"., 10000000, then loops back to 00000001. Subsequently, display the counter status

using LEOs. (10)

• The counter must increment only after you release the switch.
• You are to write the interrupt service routine to allow another interrupt to execute
in the middle of the current interrupt.
• You can assume the switches are perfect and do not produce any bouncing.
(b) In the context of Analog-to-digital conversion in microcontrollers explain the

following terms with the help of figure(s). (5+5=10)

(i) Sampling error
(ii) Quantization error
(c) The following code (Figure I(c» is a faulty code that was designed to measure the
period of a high-frequency square wave using TIMER I input capture. Correct and

modify the code to measure the period of a low-frequency square wave. (15)
1 #include <avr/io.h>
2 #include <avr/interrupt.h>
3 #include <avr/inttypes.h>
4
5 volatile uintl6_t period;
6
7 ISR(TlMERl_CAPT_vectl

10
11
8
9
I
l
period = ICRl;
TCNTI = 0;

12 int main () {
13 TCCRIA = ObOOOOOOOO;
14 TCCRIB = Obll00000l;
15 TIMSK = ObOOOOOl00;
16 return 0;
17
Figure l(c)
Contd """ P/2
 =2=

CSE 315

2. (a) What are the difference between Harvard and von Neumann architecture? Which

one of them is the architecture of ATmega32? (5)

(b) Write five differences between Microprocessors and Microcontrollers. (10)
(c) Three SPI Slaves (SI, S2, and S3) are connected to an SPI Master (M) as shown in
Figure 2(c). Initially, each device has eight bits of data in its shift registers as shown in

the corresponding dotted box. Each device is also configured to transmit the LSB first. (10)

Determine the contents of the shift registers of the four devices after
i. 4 clock pulses
ii. 16 clock pulses

SCKf---_>---1,~ SCK
SPI MISOI<IIJE----+----iMISO SPI
.tv.1~.~.t.~.U.tv.11 ..(~1.2
..~I.'l.y.~
MOSIl-----, ~ MOSI
.1.9..1.9.1.9..1.9..J l.1.1.9..9.1.1.9..9
r--+-+--+-~SS.

+--H~SCK
-MISO SPI
,.~I.'l.y.~.f??)
~MOSI
L9...1.9.1..9 ..1.9..1.
"---+-+-+--l~SS'

L--t--l,~SCK
-MISO SPI
..(?})
,.~I.'l.y.~
L----l~ IMOSI
L..Q.Q9..Q..1..1..1.1.
+----~:SS.

Figure 2(c)

(d) A switch is connected to an ATmega32 (Figure 2(d». (10)

i. What is the problem with such a connection?
ii. How can you solve the problem without modifying the connection?

ATmega32

PAD 1---../

Figure 2(d)
Contd P/3
 =3=

CSE 315

3. (a) What is the problem associated with _de1ay-ms() function of Atmege32? Explain

with an example. (5)

(b) Write two differences between CISC and RISC. Which one of them is used in

ATmega32? (5)
(c) Suppose TIMERI of ATmega32 is operating in mode WGM = 1010 (Table 2).
Prescaler is 8. The value of ICRI is 2000, and OCRIA is 400. OCIA is configured to
be clear on compare match when up-counting and set on compare match when down-
counting. Draw the wave shape of OC IA with respect to TCNT!. Also, calculate the

duty cycle and frequency ofOCIA. (10)

(d) Suppose TIMER I of ATmega32 is nmning in mode WGM = 0100 (Table 2). The
value ofOCRIA = 32768 and OeRIB = 15625. Pin OCIA and OClE are configured
to toggle on compare match. Initially, OCIA and OClE are both low, and TCNTI = O.
Prescaler is 64. Draw the wave shape of OCIA and OCIB with respect to TCNT!.

Also, calculate the duty cycle and frequency ofOCIA and OCI B. (15)

4. (a) Write a C code for ATmega32 using TIMER I to generate a square wave signal with
period 2000~ts and high time 300J..ls.You must use Fast PWM mode for this. Refer to

Tables 2 and 3 for relevant configurations. (10)

(b) The following function (Figure 4(b)) is responsible for receiving 8-bit UART data.
However, the function is faulty. Identify the flaws and correct them with brief

explanation. (10)

unsigned char USART Receive()

{ -
while .(! (UCSRA & (1 « UDRE») ;
unsigned char data = UDR;
unsigned char status = UCSRA;
if (status & (1 «FE) I (l « DOR) I (1« PE» {
return -data;
}
return data;

Figure 4(b)

Contd P/4
 =4=
CSE 315
Contd ... Q. No.4

(c) A UART sender (X) is configured with:

UCSRA = ObOOOOOOOO;
UCSRB = ObOOOOIIOO;UCSRC = ObIOOOIIIO; UBRRL =

Ox33; UBRRH = OxOO;

A UART sender (Y) is configured with:
UCSRA = ObOOOOOOOO;
UCSRB = ObOOOIOOOO;
UCSRC = Ob10100110; UBRRL =

Ox33; UBRRH = OxOO;

X has sent a 9-bit data ObOIOOllOOI which has been received by Y. Which of frame,
data over run and parity errors will happen at Y? Briefly explain you answer. ( 15)

SECTION -B
There are FOUR questions in this section. Answer any THREE.

5. (a) Define memory-mapped and port-mapped I/O. Which I/O system is used in 8086
pP? Discuss its advantage(s) and disadvantage(s) over the other. (10)

(b) Suppose you want to access memory location 00223h to 00226h using an 8086 pP. (10)
i) Determine the minimum number of required clock cycle(s).
ii) Draw the signals (timing diagram) of BH E and AO throughout these clock
cycles.

BHE AO Accessed Bank(s) Data Bits

0 0 Both banks DO-DIS
0 I Even Bank 08-015
I 0 Odd bank 00-07
I I None None
(c) 8255 can operate in three different modes. The timing diagram of one of the modes
is given below in Figure 5(c). (15)

(Buffer full)
OBF

(Interrupt requested)
INTR

Pon

Data sent 10 por1 Dala remo\lcd (rom pan

Figure S(c)

Contd P/52
 =5=

CSE 315
Contd ... Q. No. 5(c)

Now answer the following:

i) Which mode of operation is related to the above timing diagram? What can be its
possible application(s)?
ii) What are the input and output signals (to 8255) in the figure? How do the input
signals control the output? You need to show it by pointing an alTOWfrom a change
in the input signal to the cOlTesponding change in the output signal for all cases.

6. (a) (i) Why is address decoding essential for interfacing memory components with

microprocessors? Explain with examples. (7+3=10)

(ii) In a microprocessor system, the address bus is 32-bit wide, and the memory is
word addressable. Determine the maximum allowable address for this system.
(b) Draw the necessary part from the internal block diagram of 8284A clock generator

and explain the generation process of the READY signal. (10)

(c) Figure 6(c) expands the intelTupt stmcture of8086 ~LP. (5+10=15)
i) What are the vector numbers for IR2 and IRS?
ii) Suppose the vector addresses for IR2 and IRS are 4C215h and 13D2Bh
respectively. If IR2 has higher priority than IRS and both the inten'upts are activated
simultaneously, explain the priority resolution protocol.

80286 wilh
the 82288

DO
01
02
0)
DC Low data bus
~
D6
07
I I I
I 6. i Sll
9 7
I I I I 2 2 2 2
yyy yy Y Y Y 1I1
I 2 ) 41234 74ALS244
I I I I 2 2 2 2
AAA AAAAA I 2
12) 41234 GG

OOA
I I I I
2 • 6 8 I )S 7 H~v~c 10K

U2
INn
1<{
14ALS30

Figure 6(c)

7. (a) What do pre-fetching and pipelining mean in a microprocessor system? How is

pre-fetching done in 8086 architecture? (10)

Contd P/6
 =6=

CSE 315
Contd ... Q. NO.7

(b) Mark has a laser-activated alarm system the generates edge-triggered interrupt
requests upon activation. He must interface it with his 8086 ~LPthrough the INTR pin.
But his attempts to directly connect the output interrupt signal to the INTR pin were
unsuccessful. So, Mark seeks advice from his genius little brother who pin-points the

problem in his plan and suggested a way around it. (10)

i) What was the problem with Mark's initial plan?
ii) Explain how the interrupt signal from the alarm system can be successfully
interfaced with 8086 with a circuit diagram.

(c) Suppose CS:IP = 0 154h:03BOh and DS:SI = 0 I 71h:OI EOh in an 8086 ~LP. (15)
i) Calculate the physical address for both the segment:offset pairs and comment on
the results.
ii) Calculate the amount of overlap in the code and data segment.

8. (a) Define Computer Bus. Explain the necessity of tri-state buffers to connect

components to the bus. (10)

(b) Do you agree that JG instruction is satisfied if and only if OF = SF and ZF = O?

Justify your answer with examples. (10)

(c) Chris wants to interface a mouse and a keyboard with his 8086 ~P through an 8255
PPJ. He wants to assign address A004h to the mouse and A005h to the keyboard.
Complete the cOlmection diagram of Figure 8(c) to help Chris successfully interface

the devices. (15)

Keyboard/Mouse
Microprocessor iill Pon A
INone
Imer1ace 8255

RESET Pon B Keyboard/Mouse

INone
IControi Reg.1

At
Keyboard/Mouse
Pone INone

Figure S(c)
 -- -:L_
'{ -

Figures and Tables for Section A

Table 1: Register Configurations of ATmega3Z

Name Configuration

GICR
I I . I . I - I IVSEL I IVCE I
I INTl I INTO INT2

MCUCR ITrigger- I - - I - ISCll I ISClO I

ISC01 I I I ISCOO I
codes: 00 ....•low level. 01 ....•any logical change. 10 ....•falling. 11 ....•rising
REF
ADMUX I REFSl REFSO I ADLAR MUX4 I MUX3 I I I MUX2 MUX1 I I MUXO I 51.
REFSO: 00 ....•AREF. 01 ....•AVCC. 11 ....•IntemaI2.56. ADLAR: 0 ....•Left

ADCSRA
I ADEN I ADSC I ADATE I ADIF I ADIE I ADPS2 I ADPS1 I ADPSO I
UCSRA
I RXC I TXC I UDRE I FE I DOR I PE I U2X I MPCM I
UCSRB
I RXCIE I TXCIE I UDRIE I RXEN I TXEN I UCSZ2 I RXBB I TXBB I
IUCSZ2.
URSEL UMSEL I UPM1 II UPMO USBS UCSZ1 UCSZO I
UCPOL I I I I
UCSRC UCSZ1. UCSZO: 000 ....•S-bit. 001 ....•6.bit. 010 •..• 7-bit. 011 •..• B-bit. 111 •..•9-bit
UPM1.UPMO: 00 •..• No parity. 10 •..• even parity. 11 •..• odd parity
USBS: 0 •..• 1 stoo bit. 1 •..• 2 stan bits

TCCRIA I COM1A1 I COM lAO I COM1B1 I COM1BO I FOC1A I FOC1B I WGM11 I WGM10 I
TCCRIB
ICNCl I ICES1 I
ICS12. . I WGM13 I WGM12 I CS12 I CS11 I CS10 I
CS11. CSI0: 001 ....•No prescaling. 010 ....•elk/B. 011 ....•elk/64. 100 ....•elk/256

TIMSK
I OCIEZ I TOIEZ I TICIEl I OCIE1A I OCIEIB I TOIEl I OCIEO I TOIEO I
TIFR
I OCF2 I TOV2 I ICFl I OCF1A I OCFIB I TOVl I OCFO I TOVO I

Table 2: Wave Generation Modes ofTtMERl

WGM Timer/Counter Mode of Operation TOP Update of OCRIX TOVl Flag Set on

1110 Fast PWM ICR1 BOTTOM TOP

0100 CTC OCR1A Immediate MAX

1010 Phase Correct PWM ICR1 TOP BOTTOM

Table 3: Behavior of OCIA for Fast PWM

COMIAl I COMIAO Description

0 0 Normal port operation. OC1A is disconnected.

0 1 WGM=1110. Toggle OClA. For other WGM, OClA disconnected.

1 0 Clear OC1A on compare match. Set OC1A at BOTTOM.

1 1 Set OCIA on compare match. Clear OC1A at BOTTOM.

 -0-
- 0-

(XCKfTO) PBO 1 0 PAO (ADCO)

(T1) PB1 2 PAl (ADC1)
(INT2/AINO) PB2 3 PA2 (ADC2)
(OCO/AIN1) PB3 4 PA3 (ADC3)
(SS) PB4 S PM (ADC4)
(MOSI) PBS 6 PAS (ADCS)
(MISO) PB6 7 PM (ADC6)
(SCK) PB7 B 3 PA7 (ADC7)
ItEm 9 ATMEGA32
2 AREF
vce 0 1 GND
GND 1 AVCC
XTAL2 2 PC7 (TOSC2)
XTAL1 3 PC6 (TOSC1)
(RXD) PDO 4 PCS (TDI)
(TXD) POl S PC4 (TOO)
(INTO) PD2 6 PC3 (TMS)
(INn) PD3 7 PC2 (TCK)
(OC1B) PD4 8 PCl (SDA)
(OC1A) PDS 9 PCO (SCL)
(ICP) PD6 0 PD7 (OC2)

Figure: Atmega32 MeU Pinout