Nkruti

Thanks napoleon. This is a question taken from an online tutorial. http://compnetworking.about.com/library/tests/bl081000q28.htm The answer to this question given in this tutorial is b. I was looking at option c. guess we are right :p

Thanks a lot for the good luck wishes and the advice. The D day is here . after seeing th scores that you guys got on the nov 8th test , I sure am nervous. Best of luck to all others who are taking the test on dec 13th.

In CIDR notation, which of the following Class C networks is capable of containing host 192.168.14.2? a)192.168.10.0/22 b)192.168.11.0/22 c)192.168.12.0/23 d)192.168.13.0/24

In a non-pipelined single-cycle-per-instruction processor with an instruction cache, the average instruction cache miss rate is 5%. It takes 8 clock cycles to fetch a cache line from the main memory. Disregarding data cache misses, what is the approximate average CPI (cycles per instruction)? (A) 0.45 (B) 0.714 © 1.4 (D) 1.8 (E) 2.22

:) I was trying to understand this line in your explanation Within a block, there are 4 words = 16 bytes, so 4 bits of the address are stored here Anyways , I think in the AGRE it is only the final answer that is gonna count. whatever approach we take ;) how about taking a shot at the 2 problems that are left

oops I did forget a 4 in the last line.:shy: thus the total cache size is 2^12(4*32+(32-14-2)+1)= 2^12 * 145 =580K bits Dionysus , have a look at slide 18 in this link. Hope the diagrammatic representation makes things clearer http://www.cse.psu.edu/~cg331/slides/cse331-week15.pdf

The number of bits needed to implement the cache represents the total amount of memory needed for storing all of the data, tags and valid data. One word=32 bits. Keeping this in mind 64KB=16K words=2^14 words Since we have 4 words per block No.of blocks =2^14/4 =2^12 Each block has 4*32 bits of data, a tag which is(32-14-2) bits plus a valid bit thus the total cache size is 2^12(32+(32-14-2)+1)=2^12*15 =60K Bits

Perfect Dionysus. An easy formula for the block to which the address in mapped to is Direct mapped cache with one word (Block address) modulo (no of blocks in the cache) Multiword Direct mapped cache (Block address) modulo (no of blocks in the cache) where block address =word address/no.of words in a block OR =byte address/no.of bytes in a block How about having a shot at the other two problems?

1)Here is a series of memory references given as word addresses 1,4 ,8,5,20,17,19,56,9,11,4,43,5,6,9,17.Assuming a direct mapped cache with four word blocks and a total size of 16 words,that are initially empty,label each reference as a hit/miss and show the final contents of the cache 2) how many total bits are required for a direct mapped cache of 64KB of data using 4 word blocks,assuming 32 bit address? 3) Consider three memory organisations a) One word wide organisation b) wide memory organisation c) interleaved organisation Assume cache block size is 16 words, width of organisation b is 4 words, number of banks of organisation c is 4. If the main memory latency for a new access is 10 cycles and the transfer time is 1 cycle, what are the miss penalties for each of these organisations? 4) Suppose a processor with a 16 word block size has an effective miss rate of 0.5%, CPI without cache misses is 1.2. Using the memories described above, how faster is this processor when using the wide memory than when using narrow or interleaved memories?

Yes dionysus this makes sense .Thanx for the explanation

Hi thermis, Could you please tell us as to how you arrived at option c? Thanks, Natasha

I do not have an answer key to this. I am not sure about option III. I was looking at option at answer a. Toupsz, can you comment on option III?

Q1. If n is even, and assuming that all A are distinct, what does the execution of the code below result in: for (i = 0; I A = A[n + 1 - i]; for n=2 A[0]=A[3] A[1]=A[2] For n=4 A[0]=A[5] A[1]=A[4] A[2]=A[3] A[3]=A[2] The values of A[0] and A[1] are lost. Q2. If L, a subset of {0, 1}^* is not recursive, then which of the following are / can be true: I. L' is not recursive. II. L is contained in a recursive set. III. L is infinite. Q3. Which of the following are true: I. Set associative Cache is cheaper than a direct mapped cache. II. Set associative Cache has a higher hit ratio than a Fully Associative Cache. III. Set associative has higher hit ratio than a direct mapped cache. Only III is true. Fully associative cache has the best hit ratio followed by set associative cache followed by direct mapped cache Q4. Consider the following grammar: S->A | B A->0B1 | 0 B->1A0 | 0 Is the language defined by the grammer: I. Context-Free II. Regular III. Infinite. Is the answer II and III

Hi Napoleon, Firstly I think Question B satisfies condition 1 of the master theorem. Coming to the solution using recursion trees. My drawing skills are sloppy. So let me try and explain it this way. The subproblem size at depth i is (2^i) n. the subproblem size will hit n=1 at depth i=log_2 n i.e (log n with base 2) Total cost at level i =(2^i) n The last level at depth (log_2 n) has 4^(log_2 n) nodes i.e n^2 nodes each contributing cost T(1) , for a total cost of n^2 T(1) which is theta(n^2) Now if we compute the total cost T(n)= n+2n+4n + ........... +2^(log_2 n -1) n + theta(n^2) This is what I think the summation should look like. Please correct me if I am wrong.

These questions are with regard to a previous posting http://www.TestMagic.com/forum/topic.asp?TOPIC_ID=8681 What is the value of f(n) in big-O notation? function f(n) { if (n return f(n/2) + 2*f(n/4); } Should'nt the answer be O(nlogn)? ___________________________________________________ Q12) What does the following program print? int x = 1; function f(i) { int x = 2; I *= 3; for (int j = 1; j g(j); } function g(j) { print j+x; } f(x); Consider four scenarios: dynamic scope with pass-by-value, dynamic scope with pass-by-reference, static scope with pass-by-value, static scope with pass-by-reference. Dynamic scope Pass by value: 3 4 5 Pass by reference: 3 4 5 Static scope Pass by value: 2 3 4 Pass by reference: 4 5 6 _________________________________________________________ I think the answer to static scope with pass by reference should be 2 3 4 Could someone comment?

S-> abA A->Sb A->a B-> b aA->bB which of the following is true? I) ababa can be generated by this grammar II) the language generated by this grammar is infinite III) there exists a CFG grammar for it A) II only B) I an II C)II and III D) III only E) I ,II and III

Dionysus, I don't have the answer to the question. The question is from the book Operating systems by galvin silberchatz. I however agree with your explanation. Can anyone else come up with some other explanation?

Would the answer be O(n)?

Consider a demand paging system with a paging disk that has an average acess and transfer time of 20 milliseconds. Addresses are translated through a page table in main memory,with an acess time of 1 microsecond. Thus each memory reference through the page table takes 2 accesses. To improve this time we have added a associative memory that reduces access time to one memory reference,if the page table entry is in the associative memory. Assume that 80% of the accesses are in the associative memory and that out of the remaining ,10% (or 2% of the total) cause page faults. What is the effective memory access time?

Hi dionysus , I forgot to add the picture accompanying the question. It is something like this. Main Memory | | ___________________________________ | | Cluster Memory Cluster Memory | | | | _______________ _________________ | | | | | | | | LM LM LM LM LM LM LM LM This would mean that answer to the first question is 40,000. Do you agree?

Eight processors share a common main memory, 4 to each cluster memory and each processor has its own local memory. Each processor makes 1 million memory accesses per second. 95%of these are satisfies by the local memory. 90% of the misses are satisfied by its cluster memory. 1) The no. of references made to the main memory per sec is a) 1,00,000 b) 2,00,000 c) 4,00,000 d)5,00,000 e) 2,000,000 2) If a cluster bus can support 4,000,000 references per second what is its utilisation a) 12.5 % b) 25% c)50% d)75% e)100%

The order of requests in the case of a) SCAN is 125,143,913,978,1022,1470,1509,1750,1774,130,86 b) CSCAN 125,143,913,978,1022,1470,1509,1750,1774, arm moves back to the beginning of the disc, 86,130

Can somebody clarify answer b? I think it should be 4 not 3

Thanks I was solving the question based on FIFO scheduling.

Hi zach, That was a really good explanation :) I think you are right. The answer must be x=20, y=15.