What is the size of your circuit in gates

Assignment Help Theory of Computation
Reference no: EM133522409

Computer Architecture

Question 1

Consider the problem of overflow detection from a 32-bit signed add/subtract unit. The available inputs are: a31-a0 (the 32 bits of the "a" operand; with a31 being the most significant bit and a0 being least significant bit), b31-b0 (same for the "b" operand), r31- r0 (the 32 bits of the result), and "S" an input where 0 means perform addition (a+b) and 1 means perform subtraction (a - b).

(a) Write the Truth Table for the Overflow output bit.

Hint: You should use 4 input bits: a31, b31, r31, and S.

(b) Write a sum-of-products or product-of-sums Boolean function for Overflow.

(c) Draw a logic circuit that implements the Boolean function from (b) using only AND and OR gates with inverters on complemented inputs.

(d) What is the size of your circuit in gates? Only count AND and OR gates.

(e) What is the gate delay of your circuit? Consider each AND/OR gate as a delay of 1, i.e., ignore delays caused by inverters or wires.

Question 2
Suppose an improvement on a given program is proposed for an architecture with Speedup=30. What fraction of the time must the improvement be used to achieve an overall speedup of 10 for the entire program? Hint: You should apply Amdahl's Law.

Question 3
Consider adding a register-memory addressing mode for source operands of ALU instructions to a load-store machine. The idea is to replace sequences of
LOAD R1, 0(Rb) # R1 = MEM[0 + Rb]
ADD R2, R1, R2 # R2 = R1 + R2
by the single instruction
ADD R2, 0(Rb) # R2 = R2 + MEM[0+Rb]
Assume that the new instruction will cause the clock cycle of the processor to increase by 5%. Answer the following using the instruction mix:
40% ALU, 25% Jumps, 20% Load, 10% Store, 5% Other Also assume that every instruction has the same CPI (e.g., 1.0).

(a) What percentage of loads must be eliminated for the machine with the new instruction to have at least the same performance as original?
Hint: use the Iron Law.

(b) Can this replacement be applied for all sequences of load followed by an ALU operation of the loaded value, or is there a situation where this cannot be used?

Reference no: EM133522409

Questions Cloud

Which has a published master plan : Select an institution of higher learning in your state which has a published Master Plan. Study the plan and answer the following. Do you recommend improvements
Describe climate change related issues facing your country : Describe at least two climate change related issues (poverty, food insecurity, environmental pollution, population etc.) facing your selected country.
How might this verse relate and work for you when you find : How might this verse relate and work for you when you find it difficult to work with others or complete tasks? what you are doing at work, home, and school
Study involving nurse and patient from different cultures : Create case study involving a nurse and patient from different cultures, either from your own practice situation or another source
What is the size of your circuit in gates : CS 5200 Computer Architecture, University of Colorado - Write a sum-of-products or product-of-sums Boolean function for Overflow and What is the size
What were some of the concepts that may have prompted : What were some of the concepts that may have prompted you to look at the relationship between business and society differently?
How did renaissance influence and impact european science : how did the renaissance influence and impact european science, culture, art, literature, and politics How did the renaissance influence holistic health
Write a rationale paper describing artifacts in e-portfolio : Write a rationale paper describing the artifacts in the e-portfolio and how they demonstrate skills, knowledge, understanding of theory professional disposition
Explain how you will use assessment data and analysis : Consider your selected grade level and explain the importance of using assessment data and analysis in your overall teaching practice.

Reviews

Write a Review

Theory of Computation Questions & Answers

  Finite-state machine design

Create a finite-state machine design to turn your FPGA development board into a simple programmable music box.

  Redundant sequence identi cation

Redundant sequence identi cation

  Compute a shortest superstring

Dynamic programming algorithm to compute a shortest superstring.

  Propositional and predicate logic

Write down a structural induction principle for the PlayTree free type

  Design a syntactic analyzer

Design a syntactic analyzer for the language specified by the grammar

  Design unambiguous grammar to parse expressions

Write a program would read two numbers and then print all numbers between the first and the second, inclusive. Design unambiguous grammar to parse expressions

  Consider a logic function with three outputs

Consider a logic function with three outputs,  A ,  B , and  C , and three inputs,  D ,  E , and  F . The function is defined as follows:  A  is true if at least one input is true,  B  is true

  Considering a single programmed operating system

Considering a single programmed operating system, what is the minimal total time required to complete executions of the two processes? You should explain your answer with a diagram.

  How to construct an nfa

Give a construction that assumes you are given a DFA for L and show how to construct an NFA (with or without ε-moves) to recognize sort(L).

  Equivalence classes to construct minimal dfa for language

How many equivalence classes does this relation have and what are they? Use these equivalence classes to construct the minimal DFA for the language.

  Impact of moore-s law on data center costs

Discuss the impact of Moore's law on data center costs on such things as servers and communications equipment. List at least 3 steps or recommendations your data center can take to offset some or all of the effect of Moore's law.

  Problem encountered in statements in predicate logic

How the problem would be encountered in attempting to represent the following statements in Predicate logic. it should be possible to: John only likes to see French movies.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd