System-Level Timing Performance Estimation Based on a Unifying HW/SW Performance Metric

Table 1 compares our work with state-of-the-art ML studies by examining prediction errors. While existing studies focus on reducing errors through SW implementation or HW synthesis, none offer a unified HW/SW model with low prediction times and errors. This gap highlights the need for a unified model to compare HW and SW processors at the system level. Our paper aims to address these limitations.

This subsection introduces a general mathematical model representing the execution time of a C function executed by a basic GPP (i.e., no advanced microarchitecture features, such as pipeline), refining the model proposed in [5]. To perform timing performance estimation, a model for the approximate (ideal) execution time ${\overline{T}}_k$ is required. Therefore, in a basic GPP, the ideal execution time of a generic C function is:

where $C{C}_j$ is the average number of clock cycles per statement, ${\tau }_j$ is the GPP processor’s clock period, and $N_k^I$ represents the number of executions of all assembly instructions in the generic C function when run with input data set $D_k$.

HW implementation (i.e., SPP) of a generic C function can be done using HLS tools like Bambu2, LegUp [6], or Vitis HLS3. As noted in [27], common HLS practices use an intermediate representation to capture the control and data flows of the C code. Basic Blocks (BBs) represent the code control flow at the statement level.

The visual representation of control and data flow using BBs is called Control and Data Flow Graph (CDFG). Each operation is assigned to a Functional Unit (FU) capable of executing it [1], and FUs are encapsulated within the BBs of the CDFG model, as shown in Figure 1. Each datapath within the q-th BB contains $L_{j,q}^{FU}$ functional units of type $F{U}_{j,q,v}$ (e.g., sum, mul, sub). The total propagation time (latency) depends on Integrated Circuit (IC) technologies and micro-architecture. $L_{j,q}^{FU}$ is obtained from code analysis on non-scheduled DFGs, while delays from registers and multiplexers are ignored. The actual execution time of a generic C function synthesized as an SPP is defined as:

where $T_k^{HW}$ in Eq. 2 is the execution time of the q-th BB in a generic C function synthesized as SPP $p_j$ with input data set $D_k$. $N_k^{BB}$ is the total number of executed BBs, $N_{j,q,k}^{st}$ is the number of executed statements in the q-th BB, and ${\gamma }_{j,q,v,k}$ is the latency of the v-th FU in the q-th BB. The clock period ${\tau }_j$ depends on IC technology, micro-architecture, and scheduling policy. Assuming no multi-cycling, pipelining, or chaining, ${\tau }_j$ is given by the following equation.

An average slack time (i.e., idle time of operations in a control step) can be used in multi-cycling and pipelined implementations [27] to calculate ${\tau }_j$. HLS tools allow setting a desired clock period ${\tau }_j$ (e.g., Bambu2), and aim to minimize the difference between the desired $\tau j$ and the actual $\tau j$. From Eq. 2, the simplified execution time model for a generic C function synthesized as SPP can be approximated as follows:

where ${\overline{T}}_{k,h}^{HW}$ is the average execution time of the h-th statement belonging to the q-th BB in a generic C function synthesized as SPP $p_j$ with data $D_k$ under the desired clock period ${\tau }_j^{\ast }$.

The proposed unified HW/SW performance model integrates the timing behavior of a generic C function executed on a GPP with that of the same function synthesized as an SPP, achieved through HLS tools.

For the SW side, let $N_{h,k,j}^I$ represent the number of assembly instructions needed to execute statement h of the C function on GPP $p_j$ with input data set $D_k$. This can be determined using an assembly-level execution trace [20]. The average number of executed assembly instructions ${\overline{N}}_k^I$ is:

$N_k^I$ is the total number of executed assembly instructions, and $N_k^{st}$ is the total number of executed statements for a generic C function with $D_k$. Therefore, Eq. 1 can be redefined:

According to Eq. 4, the expressions for the approximate (ideal) ${\overline{T}}_k$ can be redefined for basic GPP processors as follows:

Eq. 7 shows the total clock cycles $C{C}_{j,k}^{SW}$ needed to execute a generic C function on GPP $p_j$ with input $D_k$. This value is normalized in Eq.6 to the total number of C statements executed with input $D_k$.

For the HW side, based on Eq. 3, the number of clock cycles $C{C}_{j,k}^{HW}$ needed to execute a generic C function synthesized as an SPP can be evaluated using HLS tools2. These tools generate HDL files (Verilog or VHDL) and provide the required clock cycles for executing C functions with data $D_k$, as follows:

According to Eq. 5 and Eq. 8, a generic C function with input data $D_k$ executed by a GPP or by an SPP requires an execution time of:

The fraction within parentheses in Eq. 9 represents the unified metric Clock Cycles for C statements (CC4CS) [26]. The CC4CS metric, at the statement level of abstraction, encompasses both atoms (SW) and blocks (HW). According to Eq. 9, the empirical evaluation of the CC4CS metric across a set of HW/SW processor technologies requires a well-defined methodology for automated and repeatable operations, as shown in Figure 2.

For a specific processor $p_j$, each C function is taken from the benchmark. Random input data $D_{s,k}$ is generated and uniformly distributed within a set range. Two parallel processes then determine the clock cycles required by the target HW or SW processor to execute the function ($C{C}_{j,k}^{\frac{HW}{SW}}$) and the number of C statements executed ($N_k^{st}$), which depends only on the input data and function, not on the processor. To evaluate CC4CS across HW/SW processors, the process involves: (a) selecting target processors $p_j$; (b) choosing benchmark C functions; (c) generating input data sets $D_k$; (d) profiling C functions to find the number of executed statements $N_k^{st}$ (using tools like Gcov); (e) compiling/synthesizing C functions for each processor; (f) performing cycle-accurate simulations to extract the real execution time $\overline{t}(S{T}_k)$. This is done through ISS or HDL simulations. Each processor $p_j$ will then have a Cumulative Distribution Function (CDF) of $CC4C{S}_j$. Different compiler optimization flags can be applied, though in this work, the -O0 flag is used as proof of concept, leaving other flags for future exploration.

This work addresses the challenge of determining an estimator, ${\widehat{T}}_{s,k}$, for the actual (real) execution time of a given C function $z_s$ implemented or synthesized through both HW/SW processor technologies. The total actual (real) estimation time of a generic C function is expressed as follows:

where $\widehat{t}(S{T}_k)$ is the estimated average time to execute a statement $S{T}_k$ in a generic C function. The error to be minimized over functions and input data sets is:

According to Eq. 10, our proposed solution uses the Least Absolute Shrinkage and Selection Operator (LASSO) [7] to exploit an approach called the CC4CS LASSO Regression Approach (CLRA), as follows:

where $\theta$ depends on correction functions like, e.g., the affinity value defined in [4]. LASSO regression performs an L1 regularization that adds a penalty equal to the absolute value of the magnitude of the coefficients. LASSO solutions are quadratic programming problems best solved with dedicated software tools (e.g., Matlab). According to Eq. 11 and Eq. 12, we define the final estimation problem as follows:

where d is the number of observations (i.e., number of C function executions), $T_{s,k}$ is the execution time with input data set $D_k$, $N_k^{st}$ is the number of executed C statements with input data set $D_k$, $\lambda$ is a non-negative regularization parameter. The parameters ${\beta }_0$ and $\widehat{\beta }$ are scalar values.

In our work, we aimed to identify which classical probability distribution best fits the empirical cumulative $CC4C{S}_j$ distributions obtained via the SLIDE-x framework (e.g., Normal Gaussian, Lognormal, Beta, Weibull). These distributions were evaluated using Goodness-Of-Fit (GOF) metrics, including NLogN, BIC, AIC, and AICc. The analysis revealed that the Lognormal distribution is best for GPPs, while the Normal distribution suits SPPs, as shown in Figure 3.

We then outlined an approach to characterize GPPs and SPPs, focusing on estimating distribution parameters (mean $\mu$, standard deviation $\sigma$) for specific processors. To derive the values for GPPs, it has been applied the Moment Matching Approximation (MMA) method [33], which approximates the statistics of an empirical distribution function, with mean $\widehat{\mu }$ and square mean ${\widehat{\mu }}_2$, with a Lognormal random variable $Z=e^x$ such that $X\sim N({\mu }_x,{\sigma }_x^2)$.

The $\mu$ and $\sigma$ parameters for SPPs were set to the arithmetic mean $\widehat{\mu }$ and standard deviation $\widehat{\sigma }$ of the empirical distribution, with the fitted distribution being the Normal distribution $N(\widehat{\mu },{\widehat{\sigma }}^2)$. These parameters are shown in Figure 3. This approach allows for the performance characterization of any processor technology using $CC4C{S}_j$. Such characterizations can be included in datasheets or other relevant materials and made available for further analysis.

The predictive equations are given in Eq. 12, where ${\tau }_j$ represents the clock period of the HW/SW processor. We use the cumulative distribution function from Section 4.1 to estimate each function’s execution time as follows:

$Q_2$ represents the median of the lognormal distribution for the 8051, Atmega328/P, and LEON3 processors, while $\mu$ is the mean of the normal distribution for the Bambu SPP. To build the CLRA model, the dataset was split into 80% for training ($48\ast {10}^3$ inputs) and 20% for testing ($12\ast {10}^3$ inputs). We then used Matlab R2022b’s LASSO function with 10-fold cross-validation and the elastic net method, with alpha = 1.0.

Defining the estimation error as ${ϵ}_{s,k}=T_{s,k}-{\widehat{T}}_{s,k}$, we finally evaluate the errors for the different processors $p_j$ using Percentage Error (PE) and Mean Absolute Percentage Error (MAPE) defined as follows [7]:

In this work, we have used the $R^2$ measure of goodness of fit metric and defined an additional reliability metric as follows:

Table 2 shows Pearson correlation and slope values between clock cycles and executed C statements. Correlations for 8051 and ATmega328/P are lower ( 0.9), while LEON3 is close to 1. The slope indicates estimation uncertainty increases with input data bits for Atmega and 8051 but remains stable for LEON3 and Artix-7. The table also shows that 8051 performs worst with float data types due to the lack of an FPU, while Bambu has the lowest correlation ( 50%).

Table 3 shows the results from the CLRA approach. Generally, the table reports high reliability and $R^2$ values for most input types, with some exceptions due to underfitting caused by data inconsistency or imbalance (e.g., Atmega int32 or Bambu int8). Despite lower reliability and $R^2$ compared to other SW processors, LEON3 has the lowest mean error in PE (from $-1.37$% to 6.08%) and MAPE (from 0.34% to 2.58%) due to caches and pipelines creating a stronger linear link between executed statements and clock cycles. Atmega shows the largest errors and p-values, while 8051 has smaller errors due to its CISC architecture, which has a more linear dependency between statements and clock cycles. Artix 7 shows a smaller PE range (from $-2.12$% to 0.36%) but higher MAPE (from 6.54% to 11.84%) and stronger $R^2$ and reliability compared to SW processors. This is because synthesis in HW depends on data size rather than input values. Despite Bambu’s low correlation and higher errors for 8-bit types, the approach performs well for HW processors, with errors consistently below 10% for data types larger than 8 bits. Based on the works listed in Table 1, our approach consistently outperforms other works for SW processors like the 8051 and LEON3. For HW processors, other techniques may give better results but at the cost of longer execution times and greater resource demands [17]. Our approach, leveraging the CC4CS metric, provides accurate estimations for both HW and SW technologies at the system level. Errors are always below 10% for 8-bit CISC and 32-bit RISC processors with caches and pipelines (e.g., 67% more accurate than [14] for LEON3 with -O0 flag). Our approach also eliminates the need to compile/run target code for each architecture, using a linear LASSO model to represent processor behavior. Although computing the CC4CS metric for new processors can take hours, once completed, estimation time for new data is minimal. Solving the CLRA optimization takes around 1 minute, with execution time estimation negligible.

While extracting the initial dataset is time-consuming, our approach greatly reduces prediction times compared to Bambu, lowering prediction errors after data collection and training. The overall speed-up reaches up to 32x ($\approx$ 97%). In comparison, state of the art report a 17% reduction using NNs [15] and 43.78% with RFs [28], both lower than the LASSO model’s speed-up. Thus, our approach offers a significant speed-up over traditional HLS methods. For SW processors, the key advantage is model portability and the ability to evaluate performance across various inputs and code complexities.