Thursday, March 5, 2015

Advanced algorithms - 1st internal QB


Advanced Algorithms

  1. Draw the graphic examples of Θ, O and Ω notations and give the definitions of each notation.
  2. What are o(little oh) and ω(little omega) notations. Compare the Θ,O,Ω,o,ω notations.
  3. Ordering by asymptotic growth rates
    lg(lg*n)
    2lg*n
    (√2)lgn
    n2
    n!
    (lg n)!
    (3/2)n
    n3
    lg2n
    lg(n!)
    Pow(2,pow(2,n))
    n1/lgn
    lnln n
    lg*n
    n.2n
    nlglgn
    lnn
    1
    2lgn
    (lgn)lgn
    en
    4lgn
    (n+1)!
    √lgn
    lg*(lgn)
    2√2lgn
    n
    2n
    nlgn
    2↑(2↑(n+1))
  4. Solve the recurrence relation T(n)=2T(└n/2┘)+n using ther substitution method.
  5. Solve the recurrence relation T(n)=3T(└n/4┘)+Θ(n2) using the recursion tree method.
  6. Give the masters theorem and find the asymptotically tight bounds for the following recurrences
    a) T(n)=4T(n/2)+n
    b) T(n)=4T(n/2)+n2
    c) T(n)=4T(n/2)+n3.
  7. Give the bellman-ford algorithm and solve it for the following graph with s as the source node.



  1. Give the algorithm for sungle-source-shortest-path in a directed acyclic graph and solve it for the following digraph.



9) Describe the Johnson's algorithm for sparce-graphs.

Monday, January 26, 2015

Advanced Computer Architecture-Dec/Jan2015-VTU


Dec/Jan2015-10CS74
Advanced Computer Architecture
Time:3hrs Max.                                                                                        Marks:100
PART-A
  1. a) Define Computer Architecture. Illustrate the seven dimensions of an ISA.
    b) Find the die yield for dies that are 1.5 cm on a side and 1.0 cm on a side assuming a defect density of 0.4 per cm2 and α is 4.
    c) Define amdahl's law. Derive an expression for CPU clock as a function of instruction count. Clocks per instruction and clock cycle time.
  2. a) What is pipelining? With neat diagram, explain the classic five stage pipeline for RISC processor.
    b) Consider unpipelined processor. Assume that it has a 1ns clock cycle and that it uses 4 cycles for ALU operations and branches and 5 cycles for memory operations. Assume that the relative frequencies of these operations 40%, 20% and 40% respectively. Suppose that due to clock skew and setup, pipelining the processor adds 0.2ns of overhead to the clock. Ignoring any latency impact, how much speedup in the instruction execution rate will be gain from pipeline?
    c) Explain different techniques in reducing pipeline branch penalties.
  3. a) Explain true data dependence, name dependence and control dependence, with an example.
    b) What is Correlating Predictors? Explain with example.
    c) With a neat diagram give the basic structure of Tomasulo based MIPS FP unit and explain various fields of reservation station.
  4. a) Explain exploiting ILP using dynamic scheduling multiple issue and speculation.
    b) Explain Pentium 4 pipeline supporting multiple issue with speculation.
    c) Explain in detail, Branch-Target buffers.
                    PART-B
  1. a) Explain the basic schemes for enforcing coherence in a shared memory multiprocessor system.
    b) Explain the taxonomy of parallel architecture.
    c) Suppose you want to achieve a speedup of 80 with 100 processors. What fraction of the original computation can be sequential?
  2. a) Explain four memory hierarchy questions, in detail.
    b) Explain in brief, the types of basic cache optimization.
    c) Define Virtual Memory and describe its features.
  3. a) Which are the major categories of advanced optimizations of cache performance? Explain any one in detail.
    b) Describe the technique to improve memory performance inside DRAM chip.
    c) Explain the process of protecting via virtual machines.
  4. a) Explain detecting and enhancing loop level parallelism for VLIW.
    b) Explain Intel-IA 64 architecture, with a neat diagram.
    c) Write a brief note on predicated instructions.

    Accuracy of the above question paper is not guaranteed.
    Here is July,2014 Question Paper.

Thursday, December 4, 2014

Embedded Computing Systems-10CS72-Question PaperDec/Jan,2014

Since the VTU scheme changed to 2010 in Aug,2013 there are only two question papers to refer to. Dec/jan 2014 and June/July 2014.
(Word Format)

1 a) What is an embedded system? Explain the purpose of ES? List its major application areas
 and give one example for each.-8M
b) Differentiate the following, with an example:
i) Microprocessor and microcontroller  
ii) Embedded system and general purpose computers.-6M
c) Write a requirement chart for digital camera.-3M
d) List challenges of embedded computing system design. Explain briefly any two challenges. -3M

2 a) What are the major difference between Von neuman and Harward architecture?-4M
b) Explain the following:
i) Restrictions of MUL instruction.
ii) Uses of MLA instruction
iii) Register indirect addressing in ARM.
iv) Write a ARM assembly code for below C- statement z=(x|22) and (y>>2)
v) Disadvantages of busy-wait IO.-7M
c) What is an interrupt? Explain with neat diagram the interrupt mechanism.-5M
d) Solve the following:
i) What is the average memory access time of machine whose hit rate is 93% with cache
 access time of 5ns and main memory access time is 80ns.-4M
ii) Calculate cache hit rate, if the cache access time is 5ns, average memory access
 time is 6.5 ns and main memory access time is 80ns.-4M

3 a) Explain with a neat diagram, the bus with a DMA controller.-5M
b) Explain the following briefly:
I) Counter
ii) Watchdog Timer
iii) Break point
iv) Timer-4M
c) Differentiate PCI and USB by their characteristics.-3M
d) Assume that the bus has a 1MHz bus clock period, width is 2 bytes per transfer, data 
transfer itself takes 1 clock cycles, address and handshaking signals before data is 2 clock
 cycles and sending ACK after data is 1 clock cycles
i) What is the total transfer time in clock cycles to transfer a total 612000 bytes of data?
ii) What is the total burst mode transfer time in clock cycle, if B=2 byte with 2 byte wide
iii) Calculate the total real time to transfer data.-8M
4 a) Consider the following ARM assembly code, which illustrate some sample C statement.
LDR LDR ADD STR LDR LDR ADD STR LDR ADD STR LDR LDR SUB STR
r0,a R1,b R2,r0,r1 R2,w R0,c R1,d R2,r0,r1 R2,x R1,e R0,r1,r2 R0,u R0,a R1,b R2,r1,r0 R2,z
Answer the following:
I) Write the sample C code fragment for the above ARM assembly code.
ii) Draw a lifetime graph that shows uses of register in register allocation for the above 
C statement
iii) Modify the obtained C code statement using operator scheduling for register allocation
iv) Draw a lifetime graph for the modified 'C' code appear.
v) Write a ARM assembly code for the modified 'C' code using register allocation.-10M
b) Consider the following 'C' code segment
if(a>b)
x=a+b;
else x=a-b;
I) Write CDFG for the above 'C' statement
ii) Generate the ARM assembly code for the above 'C' statement.-7M
c) Explain briefly different types of performance measures on programs.-3M
Part-B
5 a) What is RTOS? Explain with an example the hard real time and soft real time.-6M
b) Differentiate process and threads. What are the parameters of PCB of a process? Why 
should each process have a distinct PCB?-8M
c) What is the significance of spin lock?-2M
d) What is semaphores? Explain briefly the different types of semaphores?-8M

6 a) Explain with neat diagram, the concept of memory mapped object.-8M
b) Explain the following:
I) Message passing
ii) Remote procedure call for IPC.-6M
c) What are the factors needs to be evaluated in selection of an RTOS? Explain.-6M

7 a) Explain with neat diagram the various fields of IP packet.-8M
b) List the features of internet LAN.-4M
c) With neat diagram, explain the various fields of CAN frame.-6M
d) Briefly explain any two features of HTTP protocols.-2M

8 a) Explain the following
I) Simulator
ii) Target system
iii) Debugging
iv) Logic analyzer-8M
b) Explain features advantages and limitations of simulator based debugging.-6M
c) Explain the types of multitasking.-6M
 
Typographical errors are regretted.... 

Sunday, November 30, 2014

Advanced Computer Architecture-June/July2014-VTU-Question Paper




1a) Define computer architecture. List and explain four important technologies, which lead to improvements in computer systems. 10M
b) Find the number of dies per 300 mm wafer for a die that is 1.5 cm on a side. 2M
c) Define Amdahls law. Derive an expression for CPU clock as a function of instruction count, clock per instruction and clock cycle time.-8M

2 a) List three major hurdles of pipelining. Explain the concept of minimizing data hazards stalls by forwarding. -10M
b) Briefly explain how the MIPS instructions can be implemented in at most five clock cycles. -5M
c) List and explain five different ways of classifying exceptions in a computer system.-5M

3a) What is instruction level parallelism? Explain control dependence using code fragment.-8M
3b) Explain the states in 2-bit prediction scheme used for dynamic branch prediction. -6M
3c) With a neat diagram, explain the basic structure of a MIPS floating point unit using Tomasulo's algorithm.-6M

4a) With a neat diagram, explain the four steps involved in executing instructions using hardware based speculation.-10M
b) What is branch target buffer? With a neat diagram, explain the steps when using branch target buffer for a simple five stage pipeline.-10M

5 a) To achieve a speedup of 80 with 100 processors what fraction of the original computation can be sequential?-4M
b) Explain the two cache coherence protocols used for enforcing coherence.-6M
c) Explain directory based cache coherence for a distributed memory multiprocessor system along with the state transition diagram.-10M

6 a) List and explain any four basic cache optimization techniques.-10M
b) With a neat diagram explain the translation buffer of fast address translation.-10M

7 a) List any five advanced optimizations of chache performance and explain briefly the compiler optimization to reduce miss rate.-10M
b) Explain briefly how memory protection is enforced via virtual memory and via virtual machines.-10M

8 a) Explain the architecture of IA64 intel processor and also the prediction and speculation support provided.-10M
b) Write short notes on benchmarks.-5M
c) Explain the internal organization of 64M bit RAM.-5M



Accuracy of the above question paper is not guaranteed.
View all units question bank(ACA from july2010 upto july2012).... here.

Embedded Computing Systems-10CS72-Question-Paper -June/July-2014



1a) Give the characteristics and constraints of embedded system.-4M
b) Explain the challenges in embedded computing system design.-8M
c) Define design methodology. Explain the embedded system design process.-8M

2a) Differentiate between the Harvard and von-Neumann architecture.-5M
b) Define ARM processor, Explain advanced ARM features.-7M
c) What is pipelining? Explain the C55x of a seven stages pipeline with a neat diagram of ARM instructions.-8M

3 a) Write the major components of bus protocol. Explain the burst read transaction with a timing diagram.-8M
b) Describe: I) Timer    ii) Cross compiler   iii) Logic analyzer.-6M
c) With a neat sketch, explain the glue logic interface.-6M

4a) Explain the circular buffers for embedded programs.-4M
b) With a neat sketch, explain the role of assemblers and linkers in compilation process.-8M
c) Explain with example, the techniques in optimizing. -8M


5 a) What is RTOS? List and explain the different services of RTOS.-10M
b) Describe the concept of multithreading and write the comparison between thread and process.-10M

6a) Define blocking and nonblocking communication. Explain the two styles of interprocess comminication, with a example.-10M
b) What are the assumptions for the performance of a real system running processes? Mention the factors that effect context switching time and interrupt latency.-10M

7a) With a neat sketch, explain the CAN data frame format and typical bus transactions on the I2C Bus.-10M
b) Explain the ethernet packet format and IP packet structure.-10M

8a) What is a simulator? Explain the features, advantages and limitations of simulator based debugging.-10M
b) What are the improvements over firmware software debugging? Explain.-10M

Accuracy of the above question paper is not guaranteed

Sunday, November 9, 2014

Advanced Computer Architecture--- IIIrd Internal

1) Define amdahl's law and calculate overall speedup using amdahl's law. Given that a new CPU, which is 20 times faster than the original CPU, on computation, is additionally introduced, the original CPU is busy with computations 80% of the time and an i/o time is 80.

2) Define the dependability?

Assume a disk subsystem with following components and an MTTF.

-> 10 disks, each rated at 1,000,000 hours MTTF

-> 1 SCSI controller, 500,000 hours MTTF

->1 power supply, 200,000 hours MTTF

-> 1 fan, 200,000 hours MTTF

-> 1 SCSI cable 1,000,000 hours MTTF

Find the sum of Failure rate of the computer system and the overall MTTF of the system?

3) What are the trends in cost? Find the no of dies in a 300mm(30 cm) wafer for dies that is 1.5 cm on a side?

4) What are the trends in power technology? Find the die yield for dies that are 1.5 cm on a side and 1.0 cm on other side. Assume the defect density is 0.4 /cm2 and α is 4.

5) Explain the control hazard under the different clock cycles?

6) Explain the data dependencies and draw the graph for trends in technology?

7) Explain the addressing modes?

8) Explain dynamic branch prediction? And explain correlating branch predictors?

9) Explain overcoming data hazards with dynamic scheduling?

10) Draw a diagram of the basic structure of a MIPS floating point unit using Tomasulo’s algorithm with a few points explanation.

Wednesday, November 5, 2014

EMBEDDED COMPUTING SYSTEMS-QUESTION BANK-IIIrd Internal


EMBEDDED COMPUTING SYSTEMS
QUESTION BANK

UNIT – 6



  1. CASE STUDY: Telephone Answering Machine. Write the Theory of operation and requirements along with detailed specifications. 10 Marks
  2. Explain briefly the procedure of evaluating operating system performance.10M
  3. Describe various interprocess communication mechanisms. 10 Marks
  4. Explain Power Management and optimization for processes. 10 Marks
  5. Describe the following: I) CPU Metrics 5 Marks II) Timing requirements on process. 5 Marks

UNIT- 7
  1. CASE STUDY: Elevator Controller. Write the Theory of operation and requirements and architecture of elevator system. 10 Marks
  2. what is Internet? Describe Internet-Enabled systems in detail. 10 Marks
  3. What is Ethernet? Describe its functionalities in detail. 10 Marks
  4. Describe commonly used embedded networks in detail 10 Marks
  5. Describe network abstraction and message passing programming in distributed embedded architectures. 10 Marks
  6. Explain the hardware and software architectures of distributed embedded architectures. 10 Marks
  7. Define Automotive Networks with Example briefly. 10Marks
  8. How do we design a Distributed embedded system around a network. 10 Marks
  9. Describe various Networks used for Embedded systems and explain I²C BUS in detail 10 Marks.
  10. With a neat sketch, explain the CAN data frame format and typical bus transactions on the IC bus. 10 Marks
  11. Explain Ethernet format and IP structure 10 Marks