[Solution] Parameterized Branch Instruction Stream Generation Codeforces Solution

A. Parameterized Branch Instruction Stream Generation

time limit per test

15 seconds

memory limit per test

1024 megabytes

input

standard input

output

standard output

Benchmarks are popular for estimating and comparing the performance of computer systems which has always been a challenging task faced by computer architects and researchers. However, as emerging applications evolve, benchmark characteristics are known to drift with time making an optimal design using benchmarks of today not optimal for applications of tomorrow. This problem has been aptly described as, "Designing tomorrow's microprocessors using today's benchmarks built from yesterday's programs.". One of the ways to address these challenges is to supplement application benchmark suites with synthetic benchmarks.

Some researchers show that with a suitable choice of a few Microarchitecture-Independent-Characteristics (MIC) related to the instruction mix, instruction-level parallelism, control flow behavior, and memory access patterns, it is possible to generate a synthetic benchmark whose performance directly relates to that of a real-world application. The parameterized nature of this framework enables the construction of synthetic benchmarks that allow researchers to explore a wider range of the application behavior space, even when no benchmarks yet exist.

Creating a program control flow generation algorithm is one of the most difficult challenges for synthetic benchmarks. Hence, this problem focuses on generating a program control flow for synthetic benchmarks based on MICs related to the behavior of conditional branch instructions.

To describe the control flow of a program, two components are used:

• Control Flow Graph
• Route

The control flow graph is a directed graph that consists of 𝑛$n$ internal nodes and 2 special nodes (the start node and end node). Internal nodes are indexed from 1$1$ to 𝑛$n$, while the index of end node is 0$0$. The start node has no input edges and a single output edge. The end node has no output edges and can have multiple input edges. Each of the internal nodes has exactly 2 output edges and can have multiple input edges. To distinguish between these 2 output edges, they are referred to as left and right edges. Self-loops are possible in the control flow graph. An example of the control flow graph with 3 internal nodes is shown in figure 1.

Figure 1. Example of the control flow graph with 3 internal nodes

The route in the control flow graph begins at the start node and exits on the end node passing all of the internal nodes in the control flow graph at least once. All of the internal nodes can be passed multiple times on the route. If the route goes through left or right edge from an internal node, we say that the route follows to the left or right on that internal node. The length of the route is denoted as 𝑘$k$ and does not include the edge from the start node. For each of the internal nodes through which the route goes a vector of the directions (left or right) that the route took on that node can be constructed. For example, if the vector is [0, 0, 1, 1, 0] for one of the internal nodes with 0$0$ and 1$1$ denoting left and right, respectively, the route passes that node 5 times and goes left, left, right, right, and left on that node.

There are 3 microarchitecture-independent-characteristics that are used to describe program behavior and generate a program control flow with a given number of internal nodes 𝑛$n$ and a length of the route 𝑘$k$:

• Mean and standard deviation of the right output direction ratio of all internal nodes: On the route, a node is passed by multiple times and the output direction of each passing can be either left or right. Each node has a different taking right output direction ratio on the route equaling the number of times the route went right direction on that node divided by the total number of times the node was passed on the route. The mean values and population standard deviation values of the right output direction ratio of all internal nodes can therefore be calculated.
• Mean and standard deviation of the node output direction transition ratio of all internal nodes: The transition number of a node is defined as the number of times the output direction changes between two consecutive passes. If a node always takes the same output direction every time it passes a node on the route, the transition number of the node is 0$0$. If a node changes output direction every time it is passed, the transition number is 𝑁−1$N-1$, with 𝑁$N$ equaling the total number of times the node was passed on the route. The transition ratio equals the transition number divided by 𝑁−1$N-1$. Mean values and population standard deviation values of the output direction transition ratio of all internal nodes can therefore be calculated.
• Mean and standard deviation of the node correlation coefficient of all internal nodes: The output direction of a particular node is highly correlated with the output directions of previously passed nodes. The node correlation coefficient reflects the predictability of a node output direction based on the output directions of previously passed nodes. The correlation coefficient of a node is calculated by: first, using an array C[P] to keep the correlative value of a node with 𝑃$P$ nodes previously passed on the route in a sliding correlation window; second, every time a node is encountered if its output direction is the same with the 𝑖th$i_{\text{th}}$ node in the correlation window, C[i] is increased by 1$1$, otherwise, C[i] is decreased by 1$1$; third, C[i] is normalized to a range [0, 1] by dividing the absolute value of C[i] by the total number of times the node was passed on the route. At the beginning of the route, if a node has less previous nodes than correlation window size 𝑃$P$, then C[i] is updated only to the index 𝑖$i$ which is not greater than the exact number of previous nodes. Finally, max(abs(C[i])) over 𝑖$i$ is calculated as the node correlation coefficient. The mean values and population standard deviation values of the node correlation coefficient of all internal nodes can therefore be calculated.

Input

The first input line contains a number of the internal nodes in the control flow directed graph 𝑛$n$ (1≤𝑛≤105)$(1\le n\le {10}^5)$.

The second input line contains the length 𝑘$k$ (𝑛≤𝑘≤107)$(n\le k\le {10}^7)$ of the route in the control flow graph.

The third input line contains the mean and population standard deviation of the right output direction of all internal nodes as 2 floating point numbers rounded to 2 decimal places.

The fourth input line contains the mean and population standard deviation of the node output direction transition ratio of all internal nodes as 2 floating point numbers rounded to 2 decimal places.

The fifth input line contains 3 values: first, the mean and population standard deviation of the node correlation coefficient of all internal nodes as 2 floating point numbers rounded to 2 decimal places, followed by the correlation window size 𝑃$P$ (1≤𝑃≤210)$(1\le P\le 2^{10})$.

Output

The first output line should have the internal node index to show which internal node the start node is connected to. The next 𝑛$n$ lines (one for each internal node) should have the following format:

• First, an integer with a value from 0$0$ to 𝑁$N$ that shows which node (other internal node or the end node) the current internal node is connected to on the left edge.
• Second, an integer with a value from 0$0$ to 𝑁$N$ that shows which node (other internal node or the end node) the current internal node is connected to on the right edge.
• Finally, a sequence of 0$0$s and 1$1$s representing a vector of output directions that the route takes on this internal node on each passing with 0$0$ and 1$1$ denoting left and right, respectively.

Scoring

• Solution will be considered incorrect if the output program control flow does not describe the control flow graph with the provided number of internal nodes 𝑛$n$ and a route with a length 𝑘$k$.
• Solutions that time out or exceed the memory limit will be considered invalid.
• If the solution is correct, its score is calculated: first, by calculating the microarchitecture-independent-characteristics for the output program control flow generated by the solution, represented as floating point numbers rounded to 2 decimal places before score formula calculations; and second, how closely the output MIC is compared to the input (original) MIC, using the following formula:If 𝛿≥1$\delta \ge 1$, then 𝛿=1$\delta =1$. If 𝐼=0$I=0$, then 𝛿=1$\delta =1$ when 𝐼≠𝑂$I\ne O$, and 𝛿=0$\delta =0$ otherwise.
• For multiple test cases, the final score is calculated as the sum of scores of individual tests.
• If two solutions have the same score, the solution submitted first wins.
• Third-party libraries and multi-thread parallel implementation are not allowed.