Add sequencing number to instruction

[pavelkryukov]

For instrumentation, instructions should contain sequence identifier, which expresses the program order. The idea is to obtain this number as early as possible (instruction fetch is the best option).

Speculative code introduces some problem here. Since no one knows whether instruction would perform writeback or not during fetch, we have to assign sequence numbers speculatively. On pipeline flush, number should be restored so there is no "hole" in instruction sequence.

That feature allows to run functional checker in out-of-order execution, even for its simple case of simultaneous writeback.

[YanLogovskiy]

Hi, I began to work on this issue. As I understood, the idea is:

1. add variable "secuence_id" in FuncInstr class.
2. add function in elf_parser that will initialize this variables.
3. add function in FuncInstr that will change values of this variables during execution in case of flush.

Am I right?

[pavelkryukov]

add variable "secuence_id" in FuncInstr class.

Right

add function in elf_parser that will initialize this variables.

Not sure. ELF parser knows nothing about how the code should be executed.

Let me demonstrate an example. Consider we have a simple loop:

ori $r1, $zero, 0x100
label:
   addui $r1, $r1, -0x1
   bnz $r1, label

In execution, we have following flow of instructions:

   ori $r1, $zero, 0x100
   addui $r1, $r2, -0x1
   bnz $r1, label
   addui $r1, $r2, -0x1
   bnz $r1, label
   addui $r1, $r2, -0x1
   bnz $r1, label
   addui $r1, $r2, -0x1
   bnz $r1, label
   addui $r1, $r2, -0x1
   bnz $r1, label
   ...

For each instruction instance we have a FuncInstr object, and for each instance it should have a sequence_id:

   ori $r1, $zero, 0x100 [0]
   addui $r1, $r2, -0x1  [1]
   bnz $r1, label        [2]
   addui $r1, $r2, -0x1  [3]
   bnz $r1, label        [4]
   addui $r1, $r2, -0x1  [5]
   bnz $r1, label        [6]
   addui $r1, $r2, -0x1  [7]
   bnz $r1, label        [8]
   addui $r1, $r2, -0x1  [9]
   bnz $r1, label        [10]
   ...

I think the best way it to set sequence ID right after calling the instruction constructor. For doing that, you have to keep current ID in FuncSim. In PerfSim, it is more tricky due to flushes, but let's discuss it when FuncSim would be ready

[YanLogovskiy]

Hi, I have a question, am I right considering that instruction is described in BaseMipsInstr class? I am going to add secuence_id to members of this class.

[pavelkryukov]

Yes, it's OK. But you need to add it to RISCV instruction dummy as well to get your code compiled. Later, we decide whether we need a separate wrapping class for sequential-related methods.

[YanLogovskiy]

Hi, I added secuence_id variable and wanted to test it by typing make test but test has failed. So I tried to run test on simulator without my code contribution. And unfortunately, test has failed again. I have this message:

The following tests FAILED:
     12 - func_sim_test (Failed)
     13 - modules_core_test (Failed)

Can You please try to run tests on your machine?

[pavelkryukov]

Could you please push your changes to some branch and make a pull request? I advise you to update your fork to the latest master version (see manual)

[pavelkryukov]

Additionally, those tests are dependent on tt.core.out binary. Try to invoke make from traces sub-directory.

[YanLogovskiy]

I updated my repository and tried to make a pull request, but because I deleted my contribution, git says me that there is nothing to compare. Should I add my code and then make a pull request?

[pavelkryukov]

Yes, sure.

[YanLogovskiy]

Maybe I have done something wrong, but git again can't see any differences. I pressed button new pull request and add the link to my repository to compare with master. There we can see differences https://github.com/YanLo/mipt-mips/commit/6660c0ecd83dcaf275cda99c7024ee5c4d05e260#diff-d9629442ced56dd0e35314318862f90d

[pavelkryukov]

It happens because you are trying to make a pull request to your own repository. Use this button:

[pavelkryukov]

Looks like your infrastructure problems are resolved — looking forward for the next steps to complete the task.

[pavelkryukov]

@YanLo Any progress? Please let me know if there are some issues.

[YanLogovskiy]

Hi, I'm sorry for silence. I've got stuck a little because lack of knowledge of c++. I can't find the description of class FuncInstr. If I add the function in BaseMIPSInstr, it doesn't work. I will work on this issue at the afternoon.

[pavelkryukov]

@YanLo Feel free to ask questions on C++ and send code for reviews. FuncInstr does not exist any longer. We are using different template classes for MIPS and RISC-V instructions, BaseMIPSInstr and RISCVInstr respectively.

In FuncSim, FuncInstr is a "type variable". Depending on command lines options, it is either BaseMIPSInstr or RISCVInstr. Therefore, if you are using some method of FuncInstr, it should exist both in BaseMIPSInstr and RISCVInstr classes.

[YanLogovskiy]

Can you please help me with this error during compilation?

/usr/bin/ld: cannot open output file tests: Это каталог

Can it be caused by old version of g++, my is 7, it is not so old.

[pavelkryukov]

Please provide a full log: what command did you run, what directory etc.

[YanLogovskiy]

yan@yan-X555LJ:~/mipt-mips/simulator$ make
[ 52%] Built target mipt-mips-src
[ 55%] Linking CXX executable tests
/usr/bin/ld: cannot open output file tests: Это каталог
collect2: error: ld returned 1 exit status
CMakeFiles/tests.dir/build.make:280: ошибка выполнения рецепта для цели «tests»
make[2]: *** [tests] Ошибка 1
CMakeFiles/Makefile2:67: ошибка выполнения рецепта для цели «CMakeFiles/tests.dir/all»
make[1]: *** [CMakeFiles/tests.dir/all] Ошибка 2
Makefile:94: ошибка выполнения рецепта для цели «all»
make: *** [all] Ошибка 2

[pavelkryukov]

yan@yan-X555LJ:~/mipt-mips/simulator$ make

You should not run CMake inside the root directory, separate directory should be created instead. See README.md:

Create a build directory somewhere, then cd into it and run cmake /path/to/mipt-mips/simulator && make

[pavelkryukov]

I reworked README.md a little bit to make instruction more clear. Does build work for you now?

[YanLogovskiy]

yan@yan-X555LJ:~/build_dir$ cmake ../mipt-mips/simulator/CMakeLists.txt
-- Boost version: 1.58.0
-- Configuring done
-- Generating done
-- Build files have been written to: /home/yan/mipt-mips/simulator

It seems to me that I should change the path build files must be written to. Is it stated in CMake files?

[pavelkryukov]

No, it is not. There are no directives in CMakeFile to override the default behavior. Yours output is quite strange to me...

Usually CMake is invoked with path to the folder rather than to CMakeLists.txt, could you please try remove "build_dir" and do this instead:

yan@yan-X555LJ:~/build_dir$ cmake ../mipt-mips/simulator

[pavelkryukov]

OK, I found why it happens. If build directory is outside the sources directory, CMake writes build files to the source directory. As a result, output binary name 'tests' contradicts with directory of the name 'tests'.

If build directory is inside the sources directory, CMake write build files to the build directory.

I will fix the output name for the test to avoid bugs in future, but I advise you to create build directory inside sources directory:

yan@yan-X555LJ:~/mipt-mips/simulator$ mkdir build_dir && cd build_dir
yan@yan-X555LJ:~/mipt-mips/simulator/build_dir$ cmake ..
yan@yan-X555LJ:~/mipt-mips/simulator/build_dir$ make

[pavelkryukov]

I've update CMake to support builds outside sources, so now you can use both build flows.

[pavelkryukov]

@YanLo Please let me know whether your issue is resolved.

[YanLogovskiy]

I've updated my project but still: I've tried two variants

yan@yan-X555LJ:~$ cd build_mipt-mips/
yan@yan-X555LJ:~/build_mipt-mips$ cmake ../mipt-mips/simulator/CMakeLists.txt 
-- Boost version: 1.58.0
-- Configuring done
-- Generating done
-- Build files have been written to: /home/yan/mipt-mips/simulator

Or

yan@yan-X555LJ:~/mipt-mips/simulator$ mkdir build_simulator
yan@yan-X555LJ:~/mipt-mips/simulator$ cd build_simulator/
yan@yan-X555LJ:~/mipt-mips/simulator/build_simulator$ cmake ..
-- Boost version: 1.58.0
-- Configuring done
-- Generating done
-- Build files have been written to: /home/yan/mipt-mips/simulator
yan@yan-X555LJ:~/mipt-mips/simulator/build_simulator$ make
make: *** Не заданы цели и не найден make-файл.  Останов.
'''

[pavelkryukov]

What happens if you type:

yan@yan-X555LJ:~/mipt-mips/simulator$ make

?

[YanLogovskiy]

Everything has been built successfully, but I think it is not professional to build in the source directory. A lot of redundant files appears.

[pavelkryukov]

Yep, that's not very convinient, but probably you may live with it, if tests and binary work. You have to be careful commiting files, I suggest to avoid git commit -a command.

There are several ways to check what is commited and what is not, hope this information would be helpful:

1. git status -uno shows status of all the trackable files (staged for commit/not staged)
2. git diff shows changes not staged to commit in a patch manner
3. git show HEAD shows the last commit in your workspace
4. git cherry -v prints a list of commits existing in your workspace but not existing in the upstream.

Anyway, do not be afraid to commit bogus or redundant files, we'll see them during the code review process.

One more question: what CMake version do you use? Use cmake --version to get version number and id.

[YanLogovskiy]

Hi, sorry for the long response. My CMake version is 3.11.4

[pavelkryukov]

Then I have no idea. Are you able to run tests and simulation?

[YanLogovskiy]

Yes, it works

[pavelkryukov]

For PerfSim, I advise to start from the tests.

https://github.com/MIPT-ILab/mipt-mips/blob/4fbf7351b7282ce1144495372757d8594a4accec/simulator/mips/mips_instr.h#L401

This code checks whether two instructions are the same instructions. It should compare sequence identifiers now in addition to PC and byte representation.

Changing it, you have tests broken, and your target would be to make them work (TDD).

Obviously, sequence counter should be held by Fetch module.

As we discussed before, the problem is caused by speculative code: on branch mispredict, some code is flushed and another code is fetched instead. You need to the reset sequence id in the Fetch unit. To do this, you have to obtain a sequence id of the mispredicted branch, available on the branch misprediction unit (Memory module). It seems that you have to add an additional port to propagate it or combine misprediction information (flag, correct address and identifier) into a new structure.

[pavelkryukov]

Correction: FuncInstr::is_same does not perform the comparison and should not be changed in order to keep LRUCache working. Instead, dumps are compared. Implementation of dump starts TDD process of implementing sequencing in PerfSim.

[pavelkryukov]

Two weeks left before the deadline. With given tempo, the issue is not expected to be fixed before deadline.

[YanLogovskiy]

So, we shouldn't change FuncInstr::is_same function. And as I understand, it will be right to start from changing function that dumps the information about instruction, am I right?

[pavelkryukov]

it will be right to start from changing function that dumps the information about instruction, am I right?

Right. Actually, in 28 days, you could try all the approaches and decide what is right without my support.