| | 1 | == How it works? == |
| | 2 | [[Image(/chrome/site/arch.png, right)]] |
| | 3 | |
| | 4 | Hydra^''VM''^ works in four phases. Firstly, our virtual machine receives the bytecode of the program and compile it at runtime to architecture specific machine code. We consider the program as a set of ''basic blocks'', where each basic block is a sequence of non-branching instructions that ends either with a branch instruction (conditional or non-conditional) or a return. Thus, any program can be represented by a graph in which nodes represent basic blocks and edges are the control flow of the program (''execution graph''). Basic blocks can be determined at the compile time, though, we are interested more in the frequency of reachability for basic blocks. In order to collect this information, we modified the baseline compiler of [http://jikesrvm.org Jikes RVM] to plugin additional instructions at the edges of basic blocks to notify us whenever these blocks is reached. This code modification doesn't affect the behavior of the original program, we call this version of the modified program a ''profiled bytecode''. We enabled the profiled bytecode to: 1) statically detect the set of variables accessed by blocks, and 2) mark basic blocks that has input/output operations, as such blocks need special handling in the program reconstruction. |
| | 5 | |
| | 6 | Having the profiled bytecode, we can construct the program ''execution graph'' that shows basic blocks and variables as nodes and the execution flow as a weighted edge where weight denotes the frequency. The benefits of execution graph are multifold: |
| | 7 | * We can find out hot-spot portions of code by examining the hot paths of the graph. |
| | 8 | * Static data dependencies between blocks can be determined from the graph. |
| | 9 | * Parallel execution patterns of the program can be detected. |
| | 10 | We developed a variant of the execution graph, ''dynamic execution graph'', that capture the relation between the basic block and itself in the future, in this graph if basic block was accessed more than once during the lifetime of the program, it appears as different blocks in the graph. This graph is useful for detecting the dependency between multiple iterations of the loops. |
| | 11 | |
| | 12 | The third phase is the reconstruction of the program. In this phase we divide the code into, hopefully, independent parts named ''super blocks'' that represent subsets of the execution graph. Every super block doesn't overlap with other super blocks in accessed variables, and represents a long sequence of instructions, including branch statements, that commonly execute in this pattern. As a branch instruction has ''taken'' and ''not taken'' paths, the super block may contains one or both of the two paths according to the frequency of using these paths. For example, in biased branches, one of the paths is often considered so it is included into the super block leaving the other path outside the super block. While in unbiased branches, both paths may be included into the super block. Therefore, a super block has multiple exists according to which flow it chooses upon its execution. Super block has also multiple entries, as a jump or branch instruction may targets one of the basic blocks that constructs it. The ''parallelizer'' module, orchestrates the construction of super blocks and distributes them over parallel threads, which leads to out of order execution of the code. It excludes from this blocks with I/O as changing their execution order affects the program semantics. |
| | 13 | |
| | 14 | Finally, we combine and link super blocks according to their exits to form the same behavior of the original program. This phase must be done with caution to preserve data consistency and program order, because in the execution graph construction we don't use any pointer tracking technique to avoid aliasing, also memory arithmetic (like, array indexed with variables) will deceive the simple technique that we used. Thus data consistency may be affected unless additional mechanism is used. To overcome these vulnerabilities, we employ [wiki:VMTM software transactional memory] that detects any memory access violation, where each super block executing as a thread represents a transaction. Besides, program order was maintained by deferring the commit of early execution of transactions till its valid execution time. |
