I'm interested in how software emulators of old game consoles work. These must consist of an interpreter for the machine language of the emulated processor.

If I have understood correctly an interpreter, for each instruction: reads the instruction and scrolls a huge switch-case (or sequence of if-elseif-...) like structure comparing the instruction with each possible instruction in the architecture of the emulated processor, and then executes the related branch.

Is it possible to distribute the switch-case into severial thread, and give them to a parallel processor (GPGPU, FPGA, ...) ?
In my opinion, this problem is inherently parallel, because if 1 core = 1 opcode, and each core can read the next opcode, then just the right core will execute the instruction.
After finishing the execution of the current instruction, then it does the same thing for the next one.

Is it a good idea to create an interpreter (slowest type of emulation, but also the easiest type of emulator and free of problems like self-modifying code) and make it faster using distribute computing?
Each instruction means a different process for a different core
No problem with concurrency, because just one instruction branch is executed.

Is this a good idea or there is any problem?


Your understanding of the complexity of a switch or case statement is not correct. In most languages these statements make a decision based on the value of a single integer variable. If those integers are densely packed together (as they typically are when an interpreter is decoding an instruction opcode) then the compiler turns this into an $O(1)$ lookup table.

The table is simply an array of addresses. The control variable for the switch statement is used to determine the offset into the array. Then the code simply jumps to the address given at that offset in the array.

In the case where the integers are not densely packed together then the compiler builds a logarithmic-height tree of branches each of which divides the remaining range in half, like in the children's "number guessing game." So, for example, if you have a switch statement over 1000 different cases spread over the numbers 0-1000000000, then you'll be able to determine whether any given input is one of the cases, and which case, in less than 10 comparisons. (Because $\log_2 1000 < 10$.)

| cite | improve this answer | |
  • $\begingroup$ Thanks for the answer, but it wasn't the point of the question. I apologize, I wasn't very clear. The point is: is it reasonably easy to create an interpreter distributed over more thread? $\endgroup$ – incud Jul 19 '14 at 12:47
  • 1
    $\begingroup$ I answered your question. No. It is not reasonable. The reason it is not reasonable is because there is not sufficient work to do in a switch statement to make up for the overhead of starting the parallel computation. If your original understanding of how a switch statement works were correct (a big chain of if-elseif-... then the parallelization idea might be worth considering. Since that's not how a switch works, it is pointless to consider. $\endgroup$ – Wandering Logic Jul 19 '14 at 12:50
  • $\begingroup$ Yes but I was like a metaphore. In a cpu you implement a switch-case or a sequence of 'if', in a gpu you may define N process for N core, and N=number of architecture's opcode. PS: thanks for editing the question, much more clear $\endgroup$ – incud Jul 19 '14 at 12:55
  • 1
    $\begingroup$ I understand the metaphor. When you have a lot of independent computations to perform then parallelism might make sense. You do not have a lot of independent computations to perform in this case. You are trying to parallelize work that didn't need to be done in the first place. $\endgroup$ – Wandering Logic Jul 19 '14 at 13:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.