uob-hpc / simeng Goto Github PK

Creating an abstract Core interface with common functions such as tick() and hasHalted(), implemented by each core model (in-order, out-of-order, emulation) will help reduce the complexity of the main simulation wrapper, as the same interaction and handling code can be used for all models.

To remove the need to iterate over source operands to find the matching register when they are supplied, it should be possible to specify the index of the operand the value is intended for.

Suggested signature:

void supplyOperand(uint8_t index, const RegisterValue& value)

To use this updated version everywhere will require modifications to the dependency matrix logic in DispatchIssueUnit, as the index of each stored dependency will also need to be kept.

Clang 5.0 spotted a couple of conditionals that check whether an unsigned integer is less than zero:

/root/project/src/A64Instruction_execute.cc:27:16: warning: comparison of unsigned expression < 0 is always false [-Wtautological-compare]
  bool v = ((x < 0) != (result < 0));

(and the same in the other implementation of addWithCarry)

It might be worth deferring the fix for this until we have the framework for adding regression tests, since this is exactly the sort of thing we would want to cover (assuming that the above leads to incorrect instruction semantics in some way).

The in-order DecodeUnit currently only supports a single uop per macro-op. This should be extended to allow for modelling architectures with multiple uops per instruction, by stalling the pipeline behind it and issuing one uop per cycle until the instruction is fully decoded.

Remove the existing hard-coded programs found in tools/simeng/main.cc, moving them to the regression test suite if suitable (once #77 is merged).

This will also allow calling simeng with no arguments to display usage information in future.

Simple things like IPC, stalls, flushes can easily be built into the core code (and currently are). We may want to consider exposing some interfaces that would enable third-party code (plugins?) to observe the simulation to collect additional metrics, whilst keeping the core SimEng codebase clean. This approach could be used to generate additional performance-related hardware counters, but potentially also for things like power/thermal modelling.

We already have 3 different modes in which we can run the simulator. We should document these in the README, and add a -h flag what options are available.

Parameterised tests should be added to test PipelineBuffer across a variety of pipeline widths.

For consistency and identifiability, member variables of classes should end in an underscore, i.e.: value_, buffer_, etc. This is to match the syntax of private variables corresponding to same-name public getter functions, such as hasStalled() and hasStalled_.

For reasons such as waiting on memory access or communicating with an I/O device, it is possible that exception handlers may need to take multiple cycles to complete. To permit this, the current exception handling framework should be updated accordingly.

A suggested approach is to modify the Architecture::handleException function to return an object which implements an ExceptionHandler interface. This object may be ticked each cycle until it reports itself as having completed.

/** A stateful exception handler, capable of progressively processing an
 * exception over multiple cycles. */
class ExceptionHandler {
 public:
  /** Process the exception. Returns `false` if further ticks are required
   * to complete processing successfully, otherwise `true`. */
  virtual bool tick();
  /** Retrieve the exception results. */
  ExceptionResult getResults() const;
}

Core models should check whether there's an outstanding exception that requires handling each cycle, and if present, tick that instead of the rest of the core. Once complete, the exception handler can be destroyed and normal execution resumed.

This modification is required to support system calls that require reading from memory, once a memory interface (#59) is in place.

A significant proportion of the runtime is currently spent managing small regions of memory, for components such as the RegisterValue data container class - a profile of the current superscalar build showed approximately 10% of execution time (516ms over a 5.21s run) was spent either allocating or freeing space for RegisterValue data.

As a significant proportion of the data contained in RegisterValue objects are 64 bits or fewer, it is possible to store these in a local uint64_t member variable and avoid unnecessary memory management. Storing the size of the data will allow for determining whether to retrieve the local value or an allocated value when either get function is called.

A future improvement would be to use a union or std::variant to store the local member variable in the same memory space as the std::shared_ptr when it's not in use, and reduce the memory footprint of the object as a result. As std::shared_ptr implementations are typically 16 bytes, this may also allow for increasing the threshold after which allocated memory is used instead, at no extra cost.

To keep the dependency management logic clean, this is likely best implemented entirely within the DispatchIssueUnit, with the dispatch logic determining which RS to dispatch to. This may be performed by using or extending the existing PortAllocator logic - this would allow the issue port vector to remain flat.

Supporting multiple reservation stations is a requirement for modelling processors like the A64FX, or AMD's Zen architectures.

To allow execution of arbitrary files, it should be possible to pass in a binary to execute via the command-line interface. This will require the addition of an ELF-parsing component, to construct the process memory and extract and set the entry point.

Expected syntax would be to have the input file after all other flags, e.g.:

simeng outoforder ./path/to/binary

For any third-party dependencies that are bundled into the SimEng library/executable, we should probably also be installing their licenses somewhere. Note that I believe this should only apply to those used by SimEng proper (such as Capstone), and doesn't apply to third-party libraries used by the testing framework such as googletest and LLVM (for now).

Supporting uop fusion appears to be required (or at least, appears to be typically used) for split store address/data instructions, to allow multiple uops to reference and write to a single LSQ entry.

With micro-op fusion, a single micro-op may represent multiple other uops "fused" together. A "fused" uop takes a single slot in the ROB, LSQ (where applicable), and decode/rename pipeline stages, but is split into multiple uops when entering the reservation station; each of these split uops may be dispatched, executed, and written back independently. Once all "child" uops have completed, the parent is marked as ready to commit. The practical benefit of micro-op fusion over regular micro-op generation is that fewer spaces are occupied in various out-of-order buffers, and on Intel processors a macro-op that decodes to a fused uop may use one of the simple decoders instead of requiring the use of the sole complex decoder.

In practice, this will require adjustments to the Instruction interface, allowing the dispatch stage to poll an instruction to determine whether it's a fused uop, and if so, to retrieve and dispatch the component uops instead. These component uops would need to also implement the Instruction interface, but would likely only exist as a thin wrapper around their "parent" instruction, sharing much of the same metadata.

It would be useful to be able to set SIMENG_DEBUG=1 to enable printing tracing and internal state information to stdout (potentially with multiple levels of verbosity). This would be used for debugging SimEng itself, not for generating traces of program execution for micro-architectural analysis.

This would be completely disabled when building in release mode.

This functionality would be provided by macros or global functions (in the simeng namespace), using printf like variadic arguments. Usage might look something like this:

DEBUG0("An action has occurred");
DEBUG1("More information about the action - the value was %d", value);
DEBUG2("Even more information, etc.");

or

DEBUG(0, "An action has occurred");
DEBUG(1, "More information about the action - the value was %d", value);
DEBUG(2, "Even more information, etc.");

I slightly prefer the former, since the verbosity level would be validated at compile time (though an enum could be used to achieve the same in the latter).

A series of instruction-based regression tests should be added to ensure instruction sequences execute correctly and result in the correct processor state.

Sample tests should include basic register manipulation tests and memory-ordering tests. Later tests may perform simple algorithms, or perform tasks such as running multiple modes of the simulator in lockstep to ensure state consistency is maintained.

Currently, it's necessary to manually clear completed reads from a memory interface once they've been processed by a component, to prevent them from being re-processed in future. This places a burden on the component, and introduces potential problems when multiple components may use the same MemoryInterface instance (i.e., when should the clear occur?).

A trivial fix would be to handle this at the core-level, with a clear occurring at the same level as the ticking of other components. Unfortunately, the presence of zero-cycle memory requests complicates this, as a read request may have been made and immediately responded to during the same cycle, with processing due to occur the next cycle at the earliest: clearing the responses would cause these to be lost.

Several potential fixes to this may be:

• Deprecate zero-cycle memory responses. All responses must arrive the cycle after they were made, at the earliest. However, this would necessitate the introduction of a more complex in-order model that can handle multi-cycle loads, and may prevent simulation of some simpler processors.
• Make zero-cycle memory responses a first-class feature. All systems should acknowledge the potential for zero-cycle responses, and anticipate that a response may arrive synchronously, immediately after the request was made. This may slightly impact performance, as memory-related systems may end up performing unnecessary scans of the memory interface for non-zero-cycle latency models.
• Per-response clearing. Allow responses to be individually removed from the memory interface. This may introduce additional overhead, but would remove the need for clearing entirely.

Numerous Instruction operations, such as {get|set}InstructionAddress, {get|set}BranchPrediction, hasExecuted, canExecute, etc. are ISA-independent, and should be made non-virtual and moved to the base Instruction class. This will reduce the amount of effort required to implement a new ISA, and potentially provide a minor performance benefit through a reduced number of vtable lookups.

Running make test doesn't automatically rebuild the regression test executables themselves if their sources have changed. One currently has to run make && make test to ensure this is done if working on the regression tests.

There's probably a way to do this in CMake, but I couldn't work it out at quick skim (sorry!).

Prior to beginning execution, it should be possible for the simulation model to query an ISA to construct an initial register/memory state. The primary use-case for this is to allow setting the stack pointer, but this also enables writing initial state to the stack (such as command-line arguments) and will enable setting the values of read-only system registers in future.

To describe the state changes required, a data structure containing registers and memory locations to be modified, and their new values, should be returned. This data structure could also be used to describe state changes as a result of exceptions, as per #53.

Suggested call signature:

ProcessStateChange getInitialState(span<char> processMemory);

To support execution of statically compiled binaries, instruction level support must be added for the __libc_start_main routine (and referenced subroutines) which is responsible for calling main, and for terminating the process once main has completed.

We will need to add some sort of flag to to indicate that a request is already in flight.

To ensure memory operations respect program order (load/store consistency) a Load/Store Queue is required (aka Load/Store Buffers, Memory Order Buffer).

Each in-flight load/store operations should possess a space in this queue, which acts as a reference to the Instruction. When a load executes, the load/store queue should be responsible for dispatching the memory access request. Under the current flat memory model, this request will be considered as completed instantly; future versions with delayed memory request responses should pass request responses to waiting load operations once they've been completed.

When a load/store operation commits, the top of the queue should be popped. For store operations, this act should result in the value being written to memory, and a memory disambiguation check should be performed: any completed loads in the queue referencing any of the same memory locations as the store should be compared, and flushed if wrong.

Spaces in this buffer should be checked for and allocated prior to dispatch (likely during Rename, alongside ROB allocation).

We need documentation on what our workflow is and some conventions we follow. Some examples include:

• Commit style, i.e. small, atomic commits
• Commit message style, e.g. tagging, present vs past tense, full stop at the end
• Use of branches and pull requests
• Installing any git hooks or running scripts before committing, e.g. git-clang-format
• When pull request should be squashed and when they should not

The src directory needs updating to the new directory structure, defined here: https://uob-hpc.github.io/SimEng/developers.html#directory-structure

This will involve updating the build system to reflect the changes.

We need to agree on formatting and conventions before any real code starts landing. I'd strongly recommend enforcing it via clang-format, which we should be able to do via CircleCI as well.

Currently the RegisterFile class is a wrapper around a type-indexed vector containing vectors of register values: std::vector<std::vector<RegisterValue>>. To better match literature, RegisterFile should be refactored to wrap around the innermost vector (std::vector<RegisterValue>), and the outermost vector should be passed around instead.

It's possible that a separate wrapper class (RegisterFiles or RegisterFileSet) may be useful to encapsulate the RegisterFile instances and abstract away the process by which the register files are interacted with.

Execution units are currently general-purpose, and support any uop. This is unrealistic, and should be replaced with a system for specifying the "group" each uop belongs to, and the groups that each execution unit is capable of handling.

The addition of this feature also requires adding a system for assigning execution ports to uops - this appears to normally be performed during dispatch. To support a range of different port assignment algorithms, it may be worth defining a standard PortAllocator interface, with operations such as uint8_t allocate(uint16_t group), and void issued(uint16_t group) (the latter being needed for load-balancing allocators). A handful of basic models should be provided, such as round-robin and simple load-balancing implementations.

The majority of areas that deal with memory assume that all memory access is valid, when in reality access may fault due to inaccessible addresses.

A system to flag faults that occurred during memory access should be added to the memory interface specification, and systems using memory interfaces should be updated to observe these faults and raise the appropriate exception.

It should be possible for the ISA to modify the process state in response to the generation of an exception. This will enable support for both syscall and full-system emulation.

As of #49, all exceptions are fatal. The ISA should be capable of specifying whether an exception is fatal, and if not, what aspects of the process state should be modified. A possible response format would be:

struct ExceptionResult {
  /** Fatal or not */
  bool fatal;
  /** Address to resume execution from */
  uint64_t nextInstructionAddress;
  /** Registers to modify */
  std::vector<Register> modifiedRegisters;
  /** Values to set modified registers to */
  std::vector<RegisterValue> modifiedRegisterValues;
  /** Memory address/width pairs to modify */
  std::vector<std::pair<uint64_t, uint8_t>> memoryAddresses;
  /** Values to write to memory */
  std::vector<RegisterValue> memoryAddressValues;
}

In order to determine the correct output state, the ISA will need to be passed a descriptor of the current register state and memory. For the out-of-order model, this will necessitate the implementation of some form of RegisterFileSet analogue which translates architectural addresses to physical ones - this could be achieved by virtualising and sub-classing RegisterFileSet, and wrapping around the physical register file and register allocation table.

An out-of-order port arrangement with multiple load units may result in a program being unable to terminate. This was tested with multiple variants of triad.

To support modelling memory latencies, the simulator needs a common memory access interface. At a minimum, this interface should support simple read requests consisting of an address/width pair, and write requests which also supply a RegisterValue to write to the destination. To respond to these requests, the memory interface should either accept a function handle which may be called during a cycle where one or more access requests have completed, or supply some mechanism by which completed requests may be queried.

An example definition is as follows:

/** A generic memory access target. */
struct MemoryAccessTarget {
  /** The address to access. */
  uint64_t address;
  /** The number of bytes to access at `address`. */
  uint8_t size;
};

/** An abstract memory interface. */
class MemoryInterface {
 public:
  /** Request a read from the supplied target location. */
  virtual void requestRead(const MemoryAccessTarget& target) = 0;
  /** Request a write of `data` to the target location. */
  virtual void requestWrite(const MemoryAccessTarget& target, const RegisterValue& data) = 0;
  /** Retrieve all completed requests. */
  virtual span<std::pair<MemoryAccessTarget, RegisterValue>> getCompletedReads() const = 0;
};

This memory interface may be extended in future to add support for prefetching or cache control commands.

These will currently crash SimEng if the divisor is zero.

The docs currently need to be built an deployed manually, which means the online version is often out of date. CircleCI can be configured to automatically build and deploy to a GitHub pages site with a little work.

The out-of-order model should be updated to allow superscalar capabilities at each stage of the pipeline. The superscalar width should be configurable.

This change will involve:

• Increasing the size of the PipelineBuffer instances between units
• Updating units to iterate over the contents of the input buffer and service all entries
• Enabling the presence of a dynamic number of execution units, each with their own issue port
• Increasing the number of instructions the reorder buffer commits each cycle

Once the repository is public, we can auto-generate Doxygen docs and deploy to a GitHub pages site (or similar).

Consider the following instruction:

fmov d0, #1.0

Some testing shows that SimEng is treating d0 as both an input and output operand, indicating that the flags coming from Capstone are incorrect (e.g. READ+WRITE instead of just WRITE). If this is the case it should be a relatively simple fixup (similar to many other instructions that we already have to do this for), but I didn't get round to double-checking the Armv8 spec to make sure that this fmov variant is definitely supposed to zero the other vector elements rather than keeping them. Same goes for FP32 variant.

Note that this doesn't affect the correctness of emulated programs, but may affect model accuracy since it introduces an additional register dependency.

Due to dependencies on resources that can only be accessed/modified in-order, some instructions are considered serialising: all younger instructions must have completed and committed prior to their execution. The primary example of such instructions is control/system register access on ARM [Cortex A-Series Programmer Guide, Section 6.5] and x86 systems [Serializing Instructions].

In order to support these instructions, the Instruction interface should be modified to add a bool isSerializing() const function. The emulation and in-order models may safely ignore the result of this function, as all instructions are implicitly treated serially.

For the out-of-order model, if an instruction is discovered to be serialising it should be stalled at the rename stage until the reorder buffer has been drained of all instructions from the same thread, to ensure that all preceding instructions have been completed and committed.

Adding this feature will enable the addition of system/control registers, which are required for successfully initialising a full process in syscall emulation mode.

To emulate the behaviour of a user-space program without implementing instruction-level support for a full OS kernel, it's necessary to provide some degree of system-call emulation. This can currently be implemented through the Architecture::handleException call that the simulator makes when exceptions are generated. Upon receive a system-call exception, the ISA implementation can extract the syscall ID (i.e., register x8 on AArch64) and respond appropriately, returning a set of necessary process-state (register/memory) modifications.

For example, if the A64Architecture syscall handler reads an x8 value of 174 (representing the getuid syscall on Linux) it may respond with a state modification updating x0 (the return register) to 0, implying that the user is root.

To reduce the need to re-implement syscall behaviour across different ISAs, syscall logic should be extracted to a common class (i.e., simeng::kernel::Linux) which provides the necessary functions for each ISA to call; this approach will also allow for supporting other kernels such as BSD. As the syscall IDs are architecture-dependent (Linux getuid is 24 on ARMv7, 102 on x86, etc.) each ISA will need to provide a translation layer for each supported OS to read arguments from registers, and write return values back.

Some programs linked against glibc will crash if they are passed to SimEng with relative paths. I suspect we just need to canonicalise the path during the readlinkat syscall, since glibc checks the first character to see if starts with /. The crash looks like this:

$ ./bin/simeng emulation ./triad-glibc-printf
Running in Emulation mode
Starting...
../sysdeps/unix/sysv/linux/generic/dl-origin.c:48: _dl_get_origin: Assertion `linkval[0] == '/'' failed.

<then hits an svc we don't yet implement>

(note that the assertion failure is coming from an assertion inside glibc in the emulated program, not an assertion inside SimEng).

To maintain existing functionality, it might be moving existing units to a simeng::inorder namespace, and duplicating/creating out-of-order units in a simeng::outoforder namespace. The following changes to units will be needed to support a simple out-of-order model:

Decode
No longer reads registers or receives forwarded operands.

Rename (new)
Receives uops from decode. Looks up source operands in an allocation table, and allocates free physical registers for destination operands, stalling if none are available. Scoreboarding flags allocated registers as not ready.

Dispatch/Issue (new)
Reads uops from rename, adding them to a reorder buffer (and assigning a sequence ID), reading ready source operand registers, and placing them in the reservation station. Receives forwarded operands from execute, and picks ready operands for issue to execution.

Execution
Results are forwarded to dispatch/issue instead of decode.

Writeback
Written uops are flagged as ready to commit, and destination registers are flagged as ready.

In addition, the following changes to the main Core behaviour will be needed:

Committing
Each cycle the head of the ROB may be committed if ready. Any allocated destination registers are freed.

Flushing
The sequence ID of instructions is used to loop over the ROB and mark younger instructions as flushed (and thus ignored when encountered later). Early pipeline stages (Fetch->Rename) are still flushed in full, as all entries are implicitly younger. Correct register allocation state must be reconstructed, as the valid (committed) mapping of architectural -> physical registers would be lost otherwise. The prototype simulator does this by keeping a "commit table" of architectural to physical register mappings, and "replaying" the allocation of non-flushed destination registers on top of this; this is probably expensive, and there are likely better and more accurate ways of doing this.

aarch64::Instruction instances are currently generated using std::make_shared, which allocates heap space for the relevant instruction. This incurs a memory management overhead, both at construction and at destruction when the resources are freed (when the last shared pointer is deleted).

Replacing this with a pool allocator would reduce the overhead significantly and result in an estimated performance increase of 10-20%.

Generated addresses and memory data are currently held in vectors in A64Instruction. These should be replaced with arrays to reduce the number of expensive heap allocations.

Some memory-accessing instructions may generate disproportionately more addresses than the average, i.e. a 2048-bit SVE gather/scatter byte instruction may generate 256 individual memory accesses. To account for this, a "local-first" system similar to the one used by the RegisterValue class may be more appropriate: a suitably small array (2-4) is reserved for addresses, falling back to a vector when too many addresses are needed. This allows for increased performance for common, simpler memory instructions, while still permitting more complex ones.

Profiling with a test implementation using purely fixed arrays suggests that this improvement should result in a 10-15% performance increase for memory-intensive programs.

A new function should be added to the branch predictor interface, to allow branch predictor implementations to determine whether the target of a branch was mispredicted once it's been decoded, but before execution. This logic is currently implemented as Instruction::checkEarlyBranchMisprediction; moving this out of the instruction implementation and into the model/predictor allows for ISA-independent branch prediction models.

This enables the addition of more informed predictor models, such as backwards taken/forwards not taken static prediction, and return address stack predictors.

The expected function signature would be as follows:

/** Improve a branch prediction according to decoded information.
 * Returns a tuple of values, signifying whether the branch was
 * mispredicted and, if so, the updated branch target prediction. */
std::tuple<bool, uint64_t> improvePrediction(Instruction& uop);

Any changes to the prediction should be propagated to the uop via setBranchPrediction().

This change would also require the addition of numerous additional public "metadata" functions on the Instruction interface, to allow the branch predictor to request and retrieve the necessary information to make an informed decision. Examples may include isBranchConditional, isBranchImmediate, isBranchReturn, isBranchSubroutine, and getBranchTarget.

Building an L1 cache bandwidth benchmark (e.g. STREAM triad-only, no OpenMP, with small arrays), with certain compilers (e.g. Clang), currently generates extremely inaccurate results (SimEng achieves much more bandwidth than real hardware - from memory it should be around 70 GB/s per core whereas we get >100 GB/s).

The issue comes from the fact that Clang generates 128-bit ldp instructions, which will each load 32 bytes of data (2x16). Since we model a TX2 with two LSUs and do not micro-op, this means we are issuing 64 bytes of load requests every cycle (one ldp on each LSU every cycle). The LSUs in TX2 actually have a limit of 16 bytes/cycle each, so 32 bytes/cycle total.

There are two ways to address this. One option is to micro-op these instructions into two independent 16-byte loads, which is what TX2 actually does. The other option is to introduce the ability to describe the load throughput limit in the LSQ or LSUs, and buffer pending loads to resume in the next cycle once the limit has been reached (stalling if necessary).

The latter should be much simpler to implement. The former should be more accurate (since it captures more than just the bandwidth limitation), but requires drastically more implementation effort and complexity (we do not model micro-oping at all at present, and this introduces many tangential concerns).

The pipeline stages should be updated to support SMT. This will require each instruction to store a hardware thread ID, which may be queried by pipeline stages to determine the appropriate set of resources to use.

To support SMT, some pipeline resources will require per-thread duplication, e.g.:

• Program counter
• Register allocation table
  Logic that revolves around the physical registers or program counter, such as flushing, will need to be updated to respect the thread ID.

For maximum flexibility, others resources should optionally support per-thread duplication, such as the branch prediction tables (BHT, BTB, etc.). Logic such as port allocation may also be updated to supply the thread ID, to enable POWER-style per-thread execution unit partitioning.

MIT, Apache 2.0 and BSD are the frontrunners. The main differences that we would want to consider are around the patent clauses.

Essential to have this before we share with anyone outside of UoB, but probably useful to have done early anyway so we can add appropriate headers to source files etc.

Currently, both the in-order and out-of-order pipeline models define their own pipeline stage unit implementations, despite having many aspects in common. A set of generic pipeline units should be created as library components, which the core models can use, extend, or encapsulate for their own pipeline units. This will help reduce code duplication and reduce the effort needed to create future models.

In the majority of cases, the out-of-order units should be suitable to convert to generic units. The in-order decode stage behaviour (supporting register reads) may be provided by encapsulating the out-of-order decode unit.