The blog provides study material for Computer Science(CS) aspirants. Mostly says "material nahi milta, padhun kahan se.", I think If you can not find content on the Internet, then you are not a CS student. Dedicated to (Prof. Rakesh Kumar, DCSA, K.U.Kurukshetra, HARYANA, INDIA)- "Ek teacher ka bahut jyada padhna, bahut jyada jaroori hota hai."
Wednesday, January 8, 2025
Doing a PhD in Computer Science by Pankaj Jalote, Professor, IIT
Thursday, May 2, 2024
Machine language
- Explain what Beta assembly language instruction(s) are needed to load the value of a variable that has been allocated in the first 32k bytes of main memory (i.e., at an address less than 0x8000). How would your answer change if the variable was located at address outside this range (e.g., at address 0x12468).
- If the storage for the variable is located at an address less than 0x8000, the 16-bit constant field of the LD instruction can hold the complete address. Note that the 16-bit constant is sign-extended, so our address has to fit in 15 bits. So LD(R31,addr,R0) would load the contents Mem[addr] into R0 assuming addr < 0x8000. For addresses >= 0x8000 the 16-bit constant field isn't large enough to hold the address. In these cases one could use the LDR instruction to load a 32-bit address into a register and the use LD to fetch the data:
vaddr: LONG(0x12468) ... LDR(vaddr,R0) ; load address of variable into R0 LD(R0,0,R0) ; load Mem[address] into R0
- a = b + 3*c;
LD(c,R1) SHLC(R1,1,R0) ; 2*c ADD(R0,R1,R0) ; + c LD(b,R1) ADD(R1,R0,R0) ST(R0,a)
- if (a > b) c = 17;
LD(a,R0) LD(b,R1) CMPLE(R0,R1,R0) BT(R0,_L2) CMOVE(17,R0) ST(R0,c) _L2:
- if (sxt_short) { b = (b << 16) >> 16; }
LD(sxt_short,R0) BEQ(R0,_L3) LD(b,R1) SHLC(R1,16,R0) ; shift so that bit 15 is now bit 31 SRAC(R0,16,R0) ; shift back, replicating sign bit ST(R0,b)
- cjt->salary += 3752;
Assume that the salary component of the structure pointed to by cjt has a byte offset of 8 from the beginning of the structure.
LD(cjt,R1) LD(R1,8,R0) ADDC(R0,3752,R0) ST(R0,8,R1)
- a[i] = a[i-1];
LD(i,R0) SHLC(R0,2,R0) LD(R0,a-4,R1) ST(R1,a,R0)
- sum = 0;
for (i = 0; i < 10; i = i+1) sum += i;
ST(R31,sum) ST(R31,i) _L7: LD(sum,R0) LD(i,R1) ADD(R0,R1,R0) ST(R0,sum) ADDC(R1,1,R1) ST(R1,i) CMPLTC(R1,10,R0) BT(R0,_L7)
Problem 2. In block structured languages such as C or Java, the scope of a variable declared locally within a block extends only over that block, i.e., the value of the local variable cannot be accessed outside the block. Conceptually, storage is allocated for the variable when the block is entered and deallocated when the block is exited. In many cases, this means the compiler if free to use a register to hold the value of the local variable instead of a memory location.
Consider the following C fragment:
int sum = 0;
{ int i;
for (i = 0; i < 10; i = i+1) sum += i;
}
- Hand-compile this loop into assembly language, using registers to hold the values of the local variables "i" and "sum".
MOVE(R31,R2) ; R2 holds sum ST(R2,sum) MOVE(R31,R1) ; R1 holds i _L5: ADD(R2,R1,R2) ADDC(R1,1,R1) CMPLTC(R1,10,R0) BT(R0,_L5) ST(R2,sum)
- Define a memory access as any access to memory, i.e., instruction fetch, data read (LD), or data write (ST). Compare the number of total number of memory accesses generated by executing the optimized loop with the total number of memory access for the unoptimized loop (part G of the preceding problem).
- The unoptimized code has an 8 instruction loop that makes 4 data accesses; 10 loop iterations => 120 memory accesses. There are 4 additional memory accesses to initialize sum and i. Total = 124.The optimized code has a 4 instruction loop that makes 0 data accesses; 10 loop iterations => 40 memory accesses. There are 6 additional memory accesses to initializes sum and i, and to store sum at the end of the loop. Total = 46.
- Some optimizing compilers "unroll" small loops to amortize the overhead of each loop iteration over more instructions in the body of the loop. For example, one unrolling of the loop above would be equivalent to rewriting the program as
int sum = 0; { int i; for (i = 0; i < 10; i = i+2) { sum += i; sum += i+1; } }Hand-compile this loop into Beta assembly language and compare the total number of memory accesses generated when it executes to the total number of memory accesses from part (1).
MOVE(R31,R2) ; R2 holds sum ST(R2,sum) MOVE(R31,R1) ; R1 holds i _L5: ADD(R2,R1,R2) ADDC(R1,1,R0) ADD(R2,R0,R2) ADDC(R1,2,R1) CMPLTC(R1,10,R0) BT(R0,_L5) ST(R2,sum)This code has a 6 instruction loop that makes 0 data accesses; 5 loop iterations => 30 memory accesses. There are 6 additional memory accesses to initializes sum and i, and to store sum at the end of the loop. Total = 36.
Problem 3.
- Hand-assemble the following Beta assembly language program:
I = 0x5678 B = 0x1234 LD(I,R0) SHLC(R0,2,R0) LD(R0,B,R1) MULC(R1,17,R1) ST(R1,B,R0)
I = 0x5678
B = 0x1234
LD(R31,I,R0) 011000 00000 11111 0101 0110 0111 1000 = 0x601F5678
SHLC(R0,2,R0) 111100 00000 00000 0000 0000 0000 0010 = 0xF0000002
LD(R0,B,R1) 011000 00001 00000 0001 0010 0011 0100 = 0x60201234
MULC(R1,17,R1) 110010 00001 00001 0000 0000 0001 0001 = 0xA8210011
ST(R1,B,R0) 011001 00001 00000 0001 0010 0011 0100 = 0x64201234
- What C statement might have been compiled into the code fragment above?
- B[I] = B[I] * 17;
Problem 4. Hand-assemble the following Beta branch instructions into their binary representation:
- foo: BR(foo) [recall that BR(label) = BEQ(R31,label,R31)]
BEQ R31 R31 offset = -1
011101 11111 11111 1111 1111 1111 1111
- BR(bar)
bar:
BEQ R31 R31 offset = 0
011101 11111 11111 0000 0000 0000 0000
- foo = 0x100
. = 0x1000
BF(R17,foo,R31)
BEQ R31 R17 offset = (0x100 - 0x1004)/4 = 0xFC3F
011101 11111 10001 1111 1100 0011 1111
- Explain why PC-relative branch addressing is a good choice for computers like the Beta that can encode only a "small" constant in each instruction.
- Branches are used to implement conditional and looping constructs (e.g., if, while, for). So most branch targets are just a few instructions away. With PC-relative addressing, we can reach targets 32768 instructions before or 32767 instructions after the branch, independent of the actual absolute address of the branch. So used as an offset, the 16-bit constant can accommodate most branch targets even for very large programs. Used as an absolute address, branch targets would be constrained to be in the first 32K of memory.
- Suppose a different computer could encode an arbitrary 32-bit constant in an instruction (using, e.g., a variable-length instruction encoding). Would PC-relative addressing still make sense? Why?
- Even if a complete absolute address could be encoded in an instruction, PC-relative address might be much more compact since most branch targets are nearby, i.e., we could get by with a 16-bit offset instead of a 32-bit absolute address.
Problem 5.
- True or false: The Beta SUBC opcode could be eliminated since every SUBC instruction can be replaced an equivalent ADDC instruction.
- False: SUBC(Rx,0x8000,Rx) subtracts -32768 from Rx. The ADDC equivalent would add 32768 to Rx, but we can't express that constant in the signed, 16-bit constant field provided in the Beta instruction format.
- What is the binary representation for the Beta instruction SUBC(R17,12,R22)?
SUBC R22 R17 12 110001 10110 10001 0000 0000 0000 1100 = 0xC6D1000C
- A certain TA wants to know what would happen if the Beta as implemented in the lab executed 0xEDEDEDED as an instruction. What does happen?
- 0xEDEDEDED = 111011 01111 01101 1110 1101 1110 1101
The opcode field correspsonds to an illegal instruction opcode which causes the beta to take a trap (saving the PC+4 of the offending instruction in the XP register) and set the PC to ILLOP.
- Suppose that the Beta instruction BR(error) were assembled into memory location 0x87654. Assuming that the instruction works as intended (i.e., when executed, control is transferred to the first instruction in the error routine), which of the following is the best statement about the possible values for the symbol "error"?
- it depends on the first instruction in the error routine.
- it can have any 32-bit value
- it can have any 32-bit value that is a multiple of 4
- it is a multiple of 4 in the range 0x7F658 to 0x8F654 inclusive.
- it is a multiple of 4 in the range 0x67658 to 0xA7654 inclusive.
- none of the above
- (E): A branch instruction in which the branch is taken will multiply the sign-extended 16-bit literal field by 4 and add it to PC+4.
if literal = 0x8000 then new PC = 0x87654 + 4 - (8000 * 4) = 0x67658 if literal = 0x7FFF then new PC = 0x87654 + 4 + (7FFF * 4) = 0xA7654
Problem 6. The Meta is a processor similar to the Beta, except that the data paths have been modified to accommodate the addition of a new Subtract One and Branch instruction:
Usage: SOB(Ra,label,Rc)
Operation:
literal = ((OFFSET(label) - OFFSET(current inst))/4) - 1
PC = PC + 4
EA = PC + 4*SEXT(literal)
Reg[Rc] = Reg[Ra] - 1
if (Reg[Ra]- 1) != 0 then PC = EA
As with branches in the Beta, the binary encoding of the SOB instruction places the low-order 16 bits of the "literal" value in the low-order 16 bits of the instruction. The designers of the Meta implementation have used the Meta's ALU to perform the subtraction.- Suppose R1 contains the value 1. How will executing SOB(R1,label,R31) change register R1 and the PC?
- R1 is unchanged since the destination register (Rc) of the example SOB instruction is R31. Reg[R1]-1 = 0, so the branch is not taken and so the PC will point to the instruction following the SOB.
- Consider the following instruction sequence:
loop: ADD(R1,R2,R3) SOB(R4,loop,R4)Assuming the ADD instruction is placed in location 0x108 of memory, what are the contents of the low-order 16 bits of the SOB instruction?
- Actually we don't need to know the address of the ADD instruction to answer the question since the SOB instruction (like all Beta branches) uses PC-relative addressing. Remembering that the branch offset is computed from the PC of the instruction following the SOB, the correct contents of the offset field is -2 = 0xFFFE.
- A schematic for the adder circuitry in the ALU of the Meta is shown below:
What would be the correct values for OP[2:0] in order to perform a subtract (i.e., SUM = A - B)?
- SUM = A - B = A + (~B + 1). Setting OP2 = 1 and OP1 = 0 selects ~B as the XB input to the 32-bit add, setting OP0 = 1 asserts the carry in for the low-order bit of the 32-bit add and hence provides the required "+1". So OP[2:0] = 0b101.
- What would be the correct values for OP[2:0] in order to perform the decrement needed for the SOB instruction (i.e., SUM = A - 1)?
- If OP[2:0] = 0b110, the XB input is set to (B or ~B) = all ones, the two's complement representation for -1. Carry-in should be set to 0.
- Is it possible to use the logic above to do an increment (i.e., SUM = A+1)?
- Yes, OP[2:0] = 0b001, setting XB to 0 and the carry-in to 1.
Problem 7. A local junk yard offers older CPUs with non-Beta architectures that require several clocks to execute each instruction. Here are the specifications:
| Model | Clock Rate | Avg. clocks/Inst. |
|---|---|---|
| x | 40 Mhz | 2.0 |
| y | 100 Mhz | 10.0 |
| z | 60 Mhz | 3.0 |
- x: 3,600,000 instructions executed
y: 1,900,000 instructions executed
z: 4,200,000 instructions executed
- Based on the above data which machine would you choose?
- Total execution time:
x: (3,600,000 insts)(2 clocks/inst)(25 ns/inst) = 0.18 seconds
y: (1,900,000 insts)(10 clocks/inst)(10 ns/inst) = 0.19 seconds
z: (4,200,000 insts)(3 clocks/inst)(16.67 ns/inst) = 0.21 secondsX ran the benchmark the fastest.
Problem 8. Kerry DeWay is proposing to add a "Load Constant" instruction LDC(const,Rx) to the Beta instruction set. LDC loads the 32-bit constant const in register Rx. She can't convince the hardware team to implement LDC directly and consequently plans to define it as a macro. She is considering the following alternative implementations:
[1] .macro LDC(const,Rx) {
LD(.+8,Rx)
BR(.+8)
LONG(const)
}
[2] .macro LDC(const,Rx) {
PUSH(R17)
BR(.+8,R17)
LONG(const)
LD(R17,0,Rx)
POP(R17)
}
[3] .macro LDC(const,Rx) {
ADDC(R31,const >> 16,Rx)
SHLC(Rx,16,Rx)
ADDC(Rx,const & 0xFFFF,Rx)
}
Kerry tries each definition on a few test cases and convinces herself each works fine. The Quality Assurance team isn't so sure and complains that Kerry's LDC implementations don't all work for every choice of register (Rx), every choice of constant (const), and every choice of code location.- Evaluate each approach and decide whether it works under all circumstances or if it fails, indicate that it misbehaves for certain choices of Rx, const or code location.
- [1] fails if the code is located so that the LD instruction is at, e.g., address 0x7FFC since we can't represent .+8 = 0x8004 in the 16-bit literal field of the LD instruction.[2] fails for LDC(const,R17) since the POP(R17) at the end of the macro restores the old value of R17, wiping out the constant we just loaded.[3] fails for any const which has bit 15 set (e.g., 0x8000) since the final ADDC will sign-extended its literal field, adding 0xFFFF to the high half of Rx.
Problem 9. Which of the following Beta instruction sequences might have resulted from compiling the following C statement?
int x[20], y; y = x[1] + 4;
- LD (R31, x + 1, R0)
ADDC (R0, 4, R0)
ST (R0, y, R31)
- Not this one. If x[0] is stored at location x, x[1] is stored at location x + 4 since x[] is an integer array and each integer takes one word (4 bytes).
- CMOVE (4, R0)
ADDC (R0, x + 4, R0)
ST (R0, y, R31)
- Not this one. The second instructions adds the address of x[1] to R0, not the contents of x[1].
- LD (R31, x + 4, R0)
ST (R0, y + 4, R31)
- Not this one. This stores x[1] in the location following the one word of storage allocated for y.
- CMOVE (4, R0)
LD (R0, x, R1)
ST (R1, y, R0)
- Not this one. This implements y[1] = x[1].
- LD (R31, x + 4, R0)
ADDC (R0, 4, R0)
ST (R0, y, R31)
- Yes!
- ADDC (R31, x + 1, R0)
ADDC (R0, 4, R0)
ST (R0, y, R31)
- Not this one. The ADDC instruction loads the address of x plus 1 into R0.
Problem 10. An unnamed associate of yours has broken into the computer (a Beta of course!) that 6.004 uses for course administration. He has managed to grab the contents of the memory locations he believes holds the Beta code responsible for checking access passwords and would like you to help discover how the password code works. The memory contents are shown in the table below:
Address Contents (in hexadecimal) 0x100 0xC05F0008 0x104 0xC03F0000 0x108 0xE060000F 0x10C 0xF0210004 0x110 0xA4230800 0x114 0xF4000004 0x118 0xC4420001 0x11C 0x77E20002 0x120 0x77FFFFF9 0x124 0xA4230800 0x128 0x605F0124 0x12C 0x90211000
- Reconstruct the Beta assembly code that corresponds to the binary instruction encoding shown above. If the code sequence contains branches, be sure to indicate the destination of each branch.
Address Contents Opcode Rc Ra Rb Assembly 0x100 0xC05F0008 110000 00010 11111 ADDC(R31, 0x8, R2) 0x104 0xC03F0000 110000 00001 11111 ADDC(R31, 0x0, R1) 0x108 0xE060000F 111000 00011 00000 ANDC(R0, 0xF, R3) 0x10C 0xF0210004 111100 00001 00001 SHLC(R1, 0x4, R1) 0x110 0xA4230800 101001 00001 00011 00001 OR(R3, R1, R1) 0x114 0xF4000004 111101 00000 00000 SHRC(R0, 0x4, R0) 0x118 0xC4420001 110001 00010 00010 SUBC(R2, 0x1, R2) 0x11C 0x77E20002 011101 11111 00010 BEQ(R2,0x128) * 0x120 0x77FFFFF9 011101 11111 11111 BEQ(R31,0x108) ** 0x124 0xA4230800 101001 00001 00011 not an opcode 0x128 0x605F0124 011000 00010 11111 LD(0x0124,R2) 0x12C 0x90211000 100100 00001 00001 00010 CMPEQ(R1,R2,R1) * The literal in instruction 0x11c is 0x2, so the corresponding label in Beta assembly is PC + 4 + 4*literal = 0x11c + 4 + 4*2 = 0x128 ** In instruction 0x120, SEXT(literal) = -7, so the corresponding label in Beta assembly is PC + 4 + 4*literal = 0x120 + 4 + 4*(-7) = 0x124 - 0x01C = 0x108
- Further investigation reveals that the password is just a 32-bit integer which is in R0 when the code above is executed and that the system will grant access if R1 = 1 after the code has been executed. What "passnumber" will gain entry to the system?
- Let's analyze this assembly by translating it to pseudo-code:
R2 = 8; /* R2 is used as a counter */ R1 = 0; loop: R3 = R0 & 0xF; /* R3 stores the current low nibble of R0 */ R1 = R1 << 4; R1 = R3 | R1; R0 = R0 >> 4; R2 = R2 - 1; if R2 == 0 goto done; goto loop; data: 0xA4230800 done: LD(data,R2); if (R1 == R2) R1=1; else R1=0;We can see that the code shifts R1 left by a nibble (4 bits) and ors it with the low nibble (R3) of the user's entered password (R0). It then shifts the user's password right by a nibble and loops back to the beginning. It does this a total of 8 times. The net effect is to reverse the order of the nibbles in R0 and to store this into R1. The result is then compared to 0xA4230800. Therefore, in order for the entered password to be accepted, it must be the nibble-reversed version of 0xA4230800.
Thus, the "passnumber" required to enter is 0x0080324A
Monday, April 29, 2024
STACK Memory
void f1()
{
int a;
short b[4];
double c;
f2();
f3();
}
void f2()
{
int x;
char *y;
char *z[2];
f3();
}
void f3()
{
double m[3];
int n;
}
Thursday, March 7, 2024
Google Search Tips and Tricks
Syntax: time in PLACE time Los Angeles
2. Exclude Keywords in the Search
ebooks -free
3. Search for Keywords with Similar Meaning. Include Synonym Keywords in Search
nagios ~tutorial (or) debian installation ~tutorial
4. Match Any Single Word in the Search Using *
For example, if you want to search for examples of vim substitution, and you are not sure whether to search for “vim editor find and replace examples”, or “vim editor search and replace examples”, then use * , which will match either find, search or any other word, as shown below.
vim editor * and replace examples
5. Use OR in Google Search
bash examples OR programs
Note: The keyword OR should be in uppercase
6. Identify Definition a Word
Syntax: define: <word> define: tech savvy
7. Search for a Range Using ..
Syntax: text $100..$125 PDA $400..$450
8. Mathematical Calculations using Google
sqrt(10)
9. Unit Conversion using Google
kg in pound
- km in mile
- inch in feet
- acre in square feet
- sec in ms
- kilobyte in byte
- You get the idea now. Try your own conversion and see how it works.
10. Money Conversion using Google
USD in Euro (or) USD in INR
11. Searching within a Specific Website
examples site:www.thegeekstuff.com
12. Google Search for a Given Keywords (both without and with sequence)
Basic Search for a Given Keywords – Without Sequence
linux command line history examples
Basic Search with Keywords In a Given Sequence
"guide to install php5 from source"
13. Search Based on File Type
linux introduction filetype:ppt
14. Google Advanced Search Page
15. Identify Local Weather for Any City in the World using Google
Syntax: weather PLACE weather Los Angeles
Thursday, December 28, 2023
NP Complete Class
Introduction
One of the - confusing - topics in Algorithm design is the concept of NP completeness. If you search the topic on the internet you will probably find tons of articles and lectures on the subject however in this short article I will summarize it so that it is easy to remember by the average student or software engineer.
It is all about Running Time
Computational complexity analysis refers to the study of computer algorithms in terms of efficiency. Given a problem of some input size, we need to know how fast or slow it runs as the input size grows to large values. Consider the following examples:
· Looking an item up in a perfect hash table takes a constant time, theoretically speaking, no matter how big the hash table is, the item can be found instantly (assuming it exists), the algorithm is said to have a running time of O(1). This is indeed very fast.
· The running time to look up an item in a sorted binary search tree of (n) elements is O(Log(n)) for example if the number of items is (32) then the number of comparisons needed to find an element is (5) in the worst case. As you can see this is a fast algorithm
· Searching for an element in an unsorted array runs in linear time O(n). If the array contains 100 elements then you need to make 100 comparisons to find the element in the worst case. This means, the algorithm will slow down linearly as the input size grows. To be exact, the running time linearly grows as the input size becomes larger.
Polynomial versus Exponential
Algorithms with a running time function of the form O(n^k) where (k) is a constant are said to run (or solved) in polynomial time. Theoretically speaking, they are fast even if (k) is large. On the other hand, algorithms with a running time of the form O(k^n) where (k) is a constant are said to run in exponential time. These algorithms are very slow. Actually it may take a computer years to finish running the algorithm.
P, NP, NP-Complete, NP-Hard
Now we know what running time means, based on that we can classify problems into classes depending on how complex they are. I will be using plain English as opposed to mathematical terms in order to make it easy to understand.
P Problem
P means that there exists an algorithm to solve the problem which runs in polynomial time. If you are still not sure what running time or polynomial means then please read the introduction one more time.
NP Problem
NP problem means that there exists an algorithm to verify a given solution is correct in polynomial time. Note that we are talking about solution verification. We are not talking about the solution for the problem because no one has ever yet discovered a fast (polynomial) solution for NP problems nor proved the solution does not exist in the first place. NP does not mean None Polynomial, please do not say that in front of people because it is embarrassing, NP stands for non deterministic which means the problem can be solved in polynomial time BUT using none deterministic machine (of course it is not the regular computer we use every day, this computer is in the mind of some weird computer scientists. If you are interested you can research it on your own. Try to search for Turing Machine)
NP-Hard Problem
Now we know what NP means, NP-Hard problem is AT LEAST as hard as any NP problem. It could be harder, who knows. Again, when thinking about problem difficulty we are still referring to the running time of the algorithm. A harder problem takes more time to finish running.
Reduction
It feels bad when you try to solve a problem and it turns to be very hard to the extent that many people have tried it without success. In order to claim that the problem cannot be solved by many people then you need to prove that it is equivalent to some known hard problem. Reduction refers to transforming a problem to another well known (hard) problem so that people won’t dare to call you stupid. This conversion process should run in polynomial time and can be used to prove a problem is NP-Complete as we will indicate later.
NP-Complete Problem
NP-Complete problem is both NP and NP-Hard. You know what NP and NP-Hard means, so NP-Complete means a problem that is easy to verify a given solution and every problem in NP can be reduced to our problem. The hard part is proving the first example of an NP-complete problem but our friend Steve Cook did that in the 1970s. Thanks to him because he did a great job so that we are not called stupid. In few words, in order to prove that a given problem is NP-Complete then
· Show it is NP: given a solution, show that it can be verified in polynomial time
· Show it is NP-Hard: pick an already known NP-Complete problem and show that you can reduce it back to our problem in polynomial time
What is the big deal about the question P = NP?
· If P is the same as NP then this is good news, there are many interesting real life problems that could be solved very quickly.
· It is going to be really embarrassing for the folks working in computer science field because it is believed (I am assuming someone got the $1000000 prize) for long time by many people that they are not the same.
· In reality many believe they are not the same because many people knocked their heads against the wall for so long without any success and because crazy scientists need a proof a solution does not exist, it is going to be an open question.