Tag Info

There are no competitions targeting general integer programming or mixed integer programming, but there are (or were) benchmarks, such as the MIPLIB (linear) and the MINLPLIB (nonlinear). There are competitions for subsets (PB, SAT, max-SAT) and for constraint programming, as you and other answers pointed out. You can find many competitions (DIMACS ...

There are competitions for constraint satisfaction solvers. Some problems there can be readily translated to IP solvers as well. See e.g., MiniZinc challenge which has taken place yearly since 2008 or the XCSP competition.

The cost of a branch misprediction depends on the depth and width of the pipeline and not the amount of code guarded by a condition. A processor keeps fetching and decoding down the wrong path until the branch is resolved and the correct target determined. In a two-wide processor with five stage before branch resolution (a "moderate performance design", say ...

Many modern processors have predicated instructions, for example the CMOVE (conditional move) on x86 processors, lots of predicated instructions on ARM 32 bits, and a lot fewer instructions on ARM 64 bit. When these instructions are executed, there is no branching at all. For example, a conditional move "move register A to register B if a condition is true"...

There are many ways this kind of situation be handled. Clever compilers If you are are writing the contents of, lets say register 5 to the memory location 0x12345, and the next instruction is reading from the memory location 0x12345 and the variable allocated at memory location 0x12345 is not "volatile", compiler will optimize your code so that the next ...

There was a Pseudo-Boolean solver competition from 2005-2012, but (as far as I can tell) nothing since then. Integer Linear Programming is a subset of Pseudo-Boolean programming. See the 2012 competition page for results and links to other competition results.

THe answers are correct. There is a data hazard when the information stored in the "regular" location (generally a data reg) is incorrect with respect to the program flow. Here information copied in the ID stage at line 2 will be the previous value of $t1, as the new one will be copied at the end of WB stage of instruction 1 (and hence at the end of MEM ...

beq doesn't contain the destination address in the instruction, but an offset relative to the location of the instruction. For example "branch if equal to the instruction 12 words ahead of the branch instruction". You cannot execute such an instruction if you don't know what the address of the branch instruction was.

Pseudo direct addressing is not intended for relative jumps. It is an absolute jump. If you want a relative jump, don't use pseudo direct addressing. It's not correct that the limit is $2^{28}$ past the current address. Suppose the current address is 0x183020C0 (to give an example). Then pseudo direct addressing will allow jumping to any address in the ...

In MIPS-speak, these areas of memory of 28 (26+2; the +2 is because instructions are four bytes in size) bit address space (256MB) are referred to as "superblocks". Pseudo-direct addressing allows you to jump anywhere within the same superblock. It doesn't matter if it's forwards or backwards. This was never a problem in practice because it's very rare for ...

By using different phases of a clock cycle for register write and register read, the number of register file ports can be reduced. (This can reduce area and latency.) A two-read and one-write instruction would otherwise require three register file ports (or introduce a structural hazard); by using different phases of the cycle one port can be used for both ...

In designing an ISA, there are many tradeoffs that can/need to be taken. This makes it slightly challenging to answer why questions but I will do my best. In mips I am sure you are aware of the three instruction classes: I, J, and R. For this explenation I belive only I and R are relevant. Type [31-26] [25-21] [20-16] [15-11] [10-06] [05-00] R-...

"Byte addressable" means that a 32-bit address points to a single byte of memory, so if you increment that address, it points one byte further. "Word addressable" means that (on a 32-bit processor) every 32-bit address points to a 32-bit word, so if you increment that address, it points four bytes further in memory. Some machines can support both byte ...

Performance improvement is possible because the fetching of the predicted instructions happens at the same time as executing the current instruction. If you guess right, fetching the next instruction was free.

In simple implementations, byte addressable is more important for writes than for read. Because, with RAM, you read all 32 or 64 bits then steer data with a multiplexer. For writes, you need to be able to selectively update each part. (An alternative, in early DEC Alpha processors, was not to provide any byte wide access instructions, they eventually added ...

Inserting NOPs is the stall. It delays execution until the result is ready. A simple pipelined CPU will have a instruction decoder that controls the entire CPU at a low level setting control lines to each functional unit to control how it behaves. Including whether to pull in a new instruction. The decoder checks dependencies between instructions and when ...

You are absolutely, completely on the wrong path here. Predicated instructions are used to avoid branching. A predicated instruction avoids the cost of a branch plus possible penalty for a mispredicted branch. If you have 100 instructions on the if and the else side, then you would need 200 predicated instructions instead of 100 unpredicated instructions ...

The computation of instructions per cycles is a measure of the performance of an architecture, and, a basis of comparison all other things being equal.  IPC can be used to compare two designs for the same instruction set architecture, as in the question you're asking comparing two design alternatives for a MIPS architecture. Or, IPC can be used to ...

First, there is a source of confusion between the table you're showing and the diagram.  The table and diagram both use the term "ALUOp" but for the diagram this is the term for the output of the "Control" going into the "ALU control", whereas for the table this is the term for the output of the "ALU control" going into the ALU! Can't ALUcontrol tell ...

For certain instructions in certain pipeline stages, we don't care about the results or operation of one or more of the hardware's many functional units. Let's say the processor implementation has several functional units, e.g. in the ALU, for addition/subtraction, one for and/or, one for multiplication, one for division, one for shifting, and maybe even (...

Learning assembly language will be helpful for you in understanding computer architecture, because the CPU is designed to run the instructions that are part of its assembly language. So, to understand what the CPU is doing and why it was designed that way, you need to know what operations it is designed to support.

Look at data dependecies: lw $r0, 4($r0) sw $r0, 4($r0) add $r0, $r0, $r0 At line 1, $r0 is being written to. At line 2, $r0 is being read. Therefore we have a RAW hazard, read after write. There is also a WAR hazard between line 2 and 3 because the register is being written after reading it.

The hazard stems from the fact that the lw instruction updates register \$r0 at the 5th stage of the pipe (write-back) while the sw and the add instructions require the updated data at the 2nd stage of the pipe (decode/read). Putting everything on a single time line (assuming the lw execution begins at time $t=1$), the correct value of \$r0 will be ...