NeuroSchedule: A Novel Effective GNN-based Scheduling Method for High-level Synthesis
Authors: Jun Zeng
Mingyang Kou
Hailong Yao
Venue: NeurIPS 2022 Accept (2022)
Keywords: High-level synthesis
Scheduling
Graph neural network
Rank loss

Abstract: High-level synthesis (HLS) is widely used for transferring behavior-level specifications into circuit-level implementations. As a critical step in HLS, scheduling arranges the execution order of operations for enhanced performance. However, existing scheduling methods suffer from either exponential runtime or poor quality of solutions. 

This paper proposes an efficient and effective GNN-based scheduling method called NeuroSchedule, with both fast runtime and enhanced solution quality. Major features are as follows: (1) The learning problem for HLS scheduling is formulated for the first time, and a new machine learning framework is proposed. (2) Pre-training models are adopted to further enhance the scalability for various scheduling problems with different settings. Experimental results show that NeuroSchedule obtains near-optimal solutions while achieving more than 50,000x improvement in runtime compared with the ILP-based scheduling method. At the same time, NeuroSchedule improves the scheduling results by 6.10% on average compared with state-of-the-art entropy-directed method. To the best of our knowledge, this is the first GNN-based scheduling method for HLS.

NeuroSchedule: A Novel Effective GNN-based Scheduling Method for High-level Synthesis
Jun Zeng" Tsinghua University
Mingyang Kou'
Hailong Yao" Tsinghua University
Tsinghua University
Xu-Chene Yin University of Science and Technology Beijing
Haili Wang Hercules Microelectronics Co., Ltd
Abstract
High-level synthesis (HLS) widely used for transferring behavior-level specifi- cations into circuit-level implementations. As critical step in HLS, scheduling arranges the execution order of operations for enhanced performance. However, existing scheduling methods suffer from either exponential runtime poor quality of solutions.
This paper proposes an efficient and effective GNN-based scheduling method called NeuroSchedule, with both fast runtime and enhanced solution quality. Major features are as follows: (1) The learning problem for HLS scheduling is formulated for the first time, and training models are adopted to further enhance the scalability for various scheduling problems with different settings. Experimental results show that NeuroSchedule obtains near- optimal solutions while achieving more than 50,000 improvement in runtime compared with the ILP-based scheduling method. At the same time, NeuroSchedule improves the scheduling results by 6.10% on average compared with sate-of-the-ar entropy-directed method. To the best of our knowledge, this is the first GNN- based scheduling method for HLS.
machine learning framework proposed. (2) Pre-
Introduction
Recently. FPGA has been playing important role in accelerating computations from the cloud to the edge [1 2 3 5) As a reconfigurable computing device, FPGA gains increasing popularity for its high performance and great energy efficiency. However, developers are required to write programs using the hardware description language (HDL) to implement applications in FPGAs, which is time-consuming and error-prons Therefore, the utilization of FPGA's enormous computing power is limited by the cumbersome developing process.
As result, the concept of high-level synthesis (HLS) is proposed in the EDA community to speed up HIS automatically transfers high-level specifications (written high- level languages like C/C++) to behavior-level implementations (written in HDLs like Cerilog/VHDL) Figure Tareeppreenntt the whole flow of HLS. As shown the figure, HLS mainly comprises three parts: compilation, synthesis, and generation. For compilation, high-level languages are transferred to Control Data Flow Graphs (CDFGs) with the assistance of modern compilers like GCC or LLVM. During the synthesis process, hardware resources (e.g. functional units, storage, and wires) are first allocated. According to the allocated hardware resources, the operations in CDFG (such as ADD and MUL) are scheduled to certain time steps. After scheduling, the allocated hardware resources
the developing process 6
'These authors contributed equally to this work. Corresponding author: Hailong Yao (hailongyao @ lsinghua.edu.cn).
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

Synthesis
High-level language code
Compllation
Allocation
Scheduling
Binding
Generation
VHDL Verilog
az,
Frontend
Functional Units
AODd
Functional Units
x1;
V LVM
Step
RTL Architac-
x5;
x3;
V Optimization
Storage
ADDS
MULA
Step
Storage
md;
Step 2
Generation
14 ml
25 40 23;
32;
V
Connectiityy Components
ADDS
Connectivity Components
Hardware Library
Figure I: High-level synthesis flow.
bound to corresponding operations and time steps. After synthesis, the generation process generates corresponding HDLs according to the synthesized results.
Scheduling one of the most critical stages in the HLS process, which arranges the execution order of operations, and thus determines the performance of generated circuits. As depicted in Figure according to the allocated hardware resources and the dependencies between operations, the operations in CDFG are arranged in different time steps. For example, during the scheduling process, operation ADDO is scheduled to step and bound to the adder. is noteworthy that only one adder is allocated to the scheduling task. So operation ADD2 could not be scheduled to step 0 same as operation ADDO, Therefore, determining the scheduling priority for the operations the key objective of the scheduling problem. However, the scheduling problem has been proved to be NP-hard [9] And existing algorithms suffer from either unbearable long runtime or poor quality of solutions. Integer linear programming (ILP) formulation has been proposed to solve the scheduling problem optimally [TO]. However, the exponential runtime of ILP is unbearable. Therefore, various heuristic algorithms proposed to obtain sub-optimal solutions within acceptable runtime. List scheduling is one of the most famous heuristic algorithms [11]. List scheduling stores ready operations in a list and arranges them according to heuristically defined priority function. Based on the list scheduling algorithm, force-directer scheduling algorithm is proposed [12), which builds a force-distribution graph for representing the priority function. Inspired by the force-directed scheduling algorithm, Entropy-Directed Scheduling (EDS) algorithm [33 replaces the priority function with the entropy of CDFGs be scheduled. The utilization of the entropy function only speeds up the scheduling process, but also improves the quality of solutions. Different from the algorithms in the list scheduling family, an algorithm based on the system of difference constraints (SDC) proposed speed up the ILP-based algorithm. SDC-based algorithm transfers the scheduling constraints into a system of difference constraints using heuristics, which greatly reduces the number of equations to be solved. However, the SDC-based algorithm cannot guarantee the optimal solution. Therefore, the aforementioned heuristic algorithms all trade quality of solutions for runtime, which leaves large optimization space to be explored.
On the one hand, the complicated dependencies of operations in the CDFG bring great challenges to the scheduling process. On the other hand, Graph Neural Networks (GNNs) 14 great representational power of complicated graphs, which is suitable for extracting complicated relations between operations in CDFGs. Therefore, a natural idea is to adopt GNNs to tackle the scheduling problem for both fast runtime and high-quality solutions. This paper proposes the first GNN-based scheduling algorithm called NeuroSchedule. Inspired by algorithms in the list scheduling family, NeuroSchedule builds a GNN model to predict the priorities of operations the CDFG. The predicted priorities are then used to arrange the operations in CDFG to obtain the scheduling results. Major contributions of this paper are summarized as follows:
15 16] have
A learning problem for the HLS scheduling is first formulated, and then a GNN-based learning framework is proposed to effectively and efficiently solve the problem.
Pre- Pre-training models adopted to further enhance the scalability for different scheduling problems with different settings.
Experimental results indicate that NeuroSchedule obtains near-optimal solutions while achieving more than 50,000 speedup compared with the II.P-based algorithm [10]. At the same time, NeuroSchedule improves the scheduling results by 6.10% on average compared with the state-of-the-al EDS algorithm [13]
The rest of this paper organized as follows. Section 2 gives a motivating example for the GNN-
based scheduling method. Section 3 gives preliminaries and the formulation of the GaNebased

---

scheduling problem. The proposed machine learning framework is presented in Section Section 5.2 introduces NeuroSchedule, well the pre-training models adopted for enhancing the scalability. Section presents the experimental results. Finally, conclusion is drawn in Section
Node: Thype Manual EBS
ADD
MUL
ADD
MUL
ADD
MUL
ADD
ADD
0
AnB
ADD
MUL
ADD
Stop
Stop
Stop
Stap
Stop
Stop
Stop
Stop
Stup
Stop
Step
Stop
Resked
Shap
Step
Step
Step
Step
Rnadyy Mades
5009
Stop
Stop
Stop
Stea
[5]
Figure 2: A motivating Example. (a) CDFG and the priority of nodes. (b) Manually designed list scheduling result cycles). (c) Entropy-directes scheduling result cycles).
2 Motivation
As introduced in Section I the list scheduling algorithm stores ready operations in a list and schedules them according heuristically defined priority function. Here, a ready operation means all of its predecessing operations are finished and the operation could be scheduled for execution immediately. For example, Figure Σ[a,, a). node is ready when node 0 and node are finished. The process of list scheduling could be stated as follows. First, the ready operations are stored in a list. Next, the operation with the highest priority in the list picked to be scheduled to available hardware resources (e.g. adders and multipliers) for execution. After the operation is finished, the newly generated ready operations are stored in the list. The above process is iterated until all operations are successfully scheduled. From the list scheduling process, defining precise priority functions is crucial to obtain good scheduling results.
A motivating example is given in Figure 2 Figure 2 a) presents the CDFG to be scheduled, which consists of operations with 2 types (ADD and MUL). And the available hardware resources for scheduling are an adder (for ADD) and a multiplier (for MUL). Figure ([c) depicts the entropy- directed scheduling process, which takes the entropy function for the priority computation. In the figure, ready operations are colored blue and finished operations are colored green. Since the entropy priority of node 3 higher than node node 3 is scheduled before node However, scheduling node 3 first delays the scheduling of node 4, which makes the multiplier idle for 3 cycles (i.e. time steps). Consequently, the final scheduling result is not optimal. In Figure[[b) we assume there an optimal manually designed priority function. Based on the optimal priority function, node 2 is scheduled before node 3, and thus the hardware resources are fully utilized. Therefore, the scheduling algorithm based the manual function gives the optimal solution.
The success of the manually designed function motivates us build machine learning framework. which learns the priority function automatically. GNNs are an effective framework for representation learning of graphs, which follow a neighborhood aggregation scheme. In GNNs, representation vectors of nodes are computed by recursively aggregating and transforming representation vectors of their neighboring nodes [14]. Therefore, GNNs are suitable to learn the CDFG embeddings for obtaining the priority function. As result, GNN-based machine learning framework is proposed to learn the priority function. Experiments verify the effectiveness the proposed scheduling method based on GNN.

---

D
S
Train Data
GNN Model
Model Input
List Scheduling
Schedule Solution
Train A
Train Label ILP
Loss Function
Priority Predicted
Hardware Library
Input CDFG
Si
L
Figure 3: Framework for NeuroSchedule.
3 Preliminaries and Problem Formulation
CDFG. In high-level synthesis, the program in high-level language is first translated into CDFG, graph-based representation defined follows:
Definition A CDFG E) is directed graph with node set V and edge set E. Each node v E V represents an operation, e.g. add or load. Each directed edge == (Vi, U2) E E, E .... |V| represents dependency relationship between operation i; and Uj, i.e., operation Vy must be executed after the execution of operation U;.
ASAP and ALAP. The As-Soon-As- -ss-osslle (ASAP) algorithm and the As-Late-As Po-sssilee (ALAP) algorithm give the information about node flexibility during the scheduling process. For node i, V. the result of ASAP and ALAP can be formulated as follows:
max ASAP(u;) +
3(0 vi
E E, EV E e EV
ASAP(u;)
(1)
0
A(0g, U.
min ALAP (1)) 3()
E, EV E 2 EV
ALAP(()
max ASAP((e)) ((,, VNEV
(2)
Resource-constrained scheduling problem. Based on the CDFG, we have to solve the resource- constrained scheduling problem: given the number of resources, find the scheduling solution with the minimum number of execution cycles, while satisfying the given set of scheduling and resource constraints. Given functional unit set U. where
U represents a functional unit, such as an adder. Denote du, as the cycle delay of functional unit u4 Given a CDFG = EV, and let |V], schedule can be defined as S (41, f2, ..., tas fi, .2,... fn), where vi E 1,2, .... (1) 4 E N*, denoting the start cycle of operation v; E V, (2) fa U, denoting the functional unit used by operation Uy. Let L max + dj. 1 denote the total number of execution cycles. The sEl....,n
resource-constraaned scheduling problem minimizes L. which can be defined as follows:
Definition Find an optimal schedule S' (11 1/2 ... Eyy fi, 1/2 f.). such that:
a) Ve =(t,, 0;) E E, i.j E 1,2, .... f + d < t2
b) Vi j E 1,2, n, + j. J. c) L max 4 -d: is minimized.
= 14 1'1 2 dz:
EEI.....m
List scheduling. As introduced in Section [ list scheduling is an effective scheduling algorithm. divides the node set into three sets, finished nodes Vp, ready nodes VR. and unscheduled nodes Vu. Given the node priority function F, where F(v;) F(u;), Us vy E VR indicates that operation ty has a higher priority than operation Uy At each step. list scheduling algorithm chooses the node un VR schedule, where F(v))) min F(u,). A better priority function in the list scheduling V.
algorithm corresponds to better scheduling solution. As the ILsed scheduling algorithm can get the optimal scheduling results, the scheduling result S (tn, f/2, ..... f.., is a good candidate for the priority function, where F(uz)) = tl U2 E V. However, for large scheduling problems, the runtime of the Iased algorithm not acceptable. Therefore, propose the GNN model to predict the priority function.
Neural Network Model. Denoting the input data D, our model can be formulated as:
P(1) = M-MMLLIINEEMBEREEE
(3)
Our loss function can be formulated as:
L= L(P,S))
(4)

---

op type
op encoding
Adjacency
encoder
R
number of cycles of op
FFN (Regression)
ASAP
concat
GIN
Predicted Priority
Learned Node-level embeddings
op ALAP
Node-Ievel embeddings
Figure 4: Model Architecture
Details of our loss function will be introduced in Section 4 Figure shows the framework of our NeuroSchedule algorithm. The ILP-based scheduling algorithm is adopted generate the training labels for our GNN model. The output of the GNN model, i.e. P, is used by the list scheduling algorithm as the priority function, which obtains significantly enhanced scheduling solution.
Model Design
machine learning framework proposed to learn the priority function in the list scheduling algorithm. In the proposed framework, the CDFG is taken as input, and GNN model is trained to predict the priorities of the operations. This section gives the model input, the model architecture, and the selection of loss function.
4.1
Model Input
The input of GNN model includes an adjacency matrix representing graph connections and a tensor representing node features. Different node features will be selected for different problems. In the scheduling problem, the node features consist of operation type, number of cycles of the operation, along with the above-defined ASAP and ALAP.
Operation's 's type and number of cycles. As the operation type is categorical and discrete, inspired by the graph-based program representation (18], the operation type is encoded by one-hot encoding. For the number of cycles of an operation, the cycle number is directly used in the encoding. For example, if there are two types of operations (MUL,, ADD) and the cycle number of MUL operation is 1, the node feature of MUL operation could be represented as [1, 0, 1]. Here, "10" from the first "1" and second "0" in the feature denotes MUL.
Operation's 's ASAP and ALAP. Except for operation's 's type and number cycles, ASAP and ALAP also adopted in the node features. As introduced in Section 3, ASAP and ALAP represent the earliest step and the latest step that an operation could be scheduled, respectively. The ASAP and ALAP of operation indicate the operation's flexibility during scheduling. For example, the ASAP of node ADD2 in Figure 5 step 0 and the ALAP is step 1, which means node ADD2 could be scheduled between step and step Different from node ADD2, the ASAP and ALAP of node ADD3 in Figure 55 are both step 1, which means node ADD3 could only be scheduled to step 1. The reason why ASAP and ALAP are adopted in the node features is that the flexibility of an operation affects its priority during scheduling. Operations with low flexibility during scheduling tend to be the bottlenecks [13. which should be scheduled with high priority fully utilize the hardware resources.
Finally, the operation's 's type, operation's 's number cycles, along with normalized ASAP and ALAP, concatenated tensor representing node features. For example, there two operations in
ADD1 ADDZ
MUL
Step
1
Step
Step
ADDS
MULA
Step
Step
Step
Step
Step
5
Step
ADDS
Step
(3)
(b)
(c)
(d)
Figure 5: An example for ASAP, ALAP, and multi-cycle operations. (a) The CDFG. (b) The result of
ASAP, (c) The result of ALAP. (d) A special scheduling example with multi-cycle operations.
5

---

Figure 5 MUL and ADD, and the number of cycles of operations MUL and ADD are both 1. So node ADD3 could be encoded as [0, 1. 1, 0.5, 0.5]. It noteworthy that the ASAP and ALAP of an operation are normalized according to the maximum ASAP value among all the operations. The normalization is conducted because the number of operations in the CDFG varies such that using the absolute ASAP and ALAP values will bring noises.
4.2 Model Architecture
Figure presents the architecture of the proposed model. As shown in the figure, the proposed model Is composed a GNN model and a feed-forward network (FFN) model. The GNN model is adopted to learn the embedding of each operation from the operation features and graph structure, while the FFN model is utilized to conduct regression tasks for predicting operations' priorities. The workflow of the model is presented follows. First, operation features including the operation's 's type, operation's 's number of cycles, along with normalized ASAP and ALAP are concatenated into a feature tensor introduced in Section 4.1 Next, GNN model is adopted to learn operation embedding from the feature tensor and graph structure. Graph Isomorphism Network (GIN) is used as the GNN model for its strong power of learning embeddings from graph structures []4]. Finally, the learned operation embedding is fed into the FFN model for predicting the operations' priorities. In the FFN model, there are three fully-connected layers, and ReLU is adopted as the activation function
4.3 Training Settings
As depicted in Figure 4 the proposed model outputs the operations' priorities by regression. To effectively train the proposed model, dedicated training pipeline is proposed. The proposed training pipeline mainly focuses on two questions: How to acquire the regression labels; How to select the training objective function (a.k.a loss function).
Training label. As formulated in Section 3 training the priority prediction task requires collection of data D = {9k, Pi, J. where denotes CDFG's graph structure, p: denotes operation properties (such as ASAP and ALAP), and 6 denotes the training label. In the proposed training pipeline, the ILsed method is used to generate the regression labels [1O]. The details are presented as follows. The ILP-based method gives the optimal solution, which arranges CDFG's operations into suitable time steps. Obviously, operations arranged in later time steps have lower priorities than those arranged in earlier time steps. Therefore, in the proposed training pipeline, the time step obtained by the IL.P-based method (i.e. tą in Section 3) is taken as the regression label G. As mentioned in Section[4.] the time step of an operation is also normalized based on the maximum time step. which reduces the impact of noises. Figure Saaure2]gee gives an example. In the manually designed priority function, the time step could be solved by the ILseb method. As shown in the figure, the P-olsslled time steps [0, 0, 1, 2, 2, 3] are assigned to corresponding operations. After normalization, the ILo--soleed time steps are computed as [0, 0, 0.33, 0.66, 0.66, 1].
Training objective function. The mean square eгтor (MSE) function is commonly adopted for training a regression task. Given dataset D
Pt, Pt, the output of our GNN model has the form P(i) = P(g., Pt). The MSE function (P(i) G) guides the model to accurately predict the operations' priorities. However, the scheduling task cares more about the operations' relative order rather than the absolute priority values of the operations. Moreover, it takes more effort for training a model to predict the absolute value than to predict the rank. Therefore, inspired by AutoTVM (20), the following rank loss function is adopted to train the model for predicting the rank of all operations 21
C log(1 + sign(e:- PP()))
During training, the above rank loss function keeps the relative order of operations' priorities with reduced training efforts.
NeuroSchedule
5.1 Pre-training for Different Scheduling Settings
As introduced Section the input of our model consists of the operation's 's type and operation's number of cycles, along with normalized ASAP and ALAP. It works well when the numbers of

---

Algorithm NeuroSchedule algorithm.
Input: Trained network model P. CDFG G E), functional unit set U, delay array d Output: Generated schedule Sp
1: Vr + ø. Va < Ø. Vy + V. Sp +- 6, Time +- 0
2: D t encode eacodeData(Gi
3: F + run.Model(? D)
4: for in V do
vegreee
then
6: VR VR U us Vo +- Vo \
7: while [Vel < [V] do
8:
for My in U do
9:
M MAX_ AAX_LOOA,, fchosen
10:
for v in VR do
F(e.) M and (e.oonUs((u))) then
12:
t F(u)), Gchosen f- U2
13:
if Vchozen = o or uj wnwvailable((Iinne (1ime)) then
14:
continue
15:
Sp (eesert(eehoenn Mj, Time) Uj. wettnnavallaalee(Ta
16:
Time duj 1)
17:
VR + VR Vchosens VF + Vp Uchosen for Us in VR do if (Vekosen, U;) E E then E EV (Wehosen: 1z)) if ff E Vo and ingreee then
18:
19:
20:
21:
22:
VR + VR U Us. VU Ve
23:
Time Time-
functional units are fixed. However, there are various scheduling settings in real HLS cases including: (1) different operation types, (2) different number of functional units for each type, and (3) different number of cycles for different operation types. Figure gives scheduling example with 2 adders, I multiplexer, and multi-cycle operations, i.c., the MUL operation takes cycles. Therefore, for scheduling problems with different settings, specified GNN models are required to get valid solutions. However, is infeasible train GNN model for each scheduling setting due to the unbearable training efforts. Therefore, we build dataset of CDFGs with different scheduling settings, and pre-train our model with the dataset. To specify the scheduling setting, we add the number of the corresponding functional units into the node features of each operation. While dealing with specific scheduling setting, we fine-tune the model using the randomly generated data from the setting. Compared with direct training, the fine-tuning takes fewer efforts with enhanced scheduling solutions.
5.2 NeuroSchedule Algorithm
Algorithm T gives overview of the proposed NeuroSchedule algorithm, which is based the traditional list scheduling algorithm and our neural network models. The symbols in Algorithm [ defined in Section 3 We use trained network model as priority function F (line 3), and run the loop until each node the CDFG successfully scheduled (line 7). In each cycle, we try to schedule every available functional unit using the node Uchosen with the highest priority. After the node Wchosen is selected from the ready set Vz, we update the schedule Sp, and the sets Vn and Vr (line 16). Then we delete all the edges (v, Vchozen) of Vchosen (line 20). If the in-degree of us equals O, we add e into the ready set VR. Finally, the scheduling solution is obtained in Sp.
6 Experiments
The proposed GNN-based scheduler implemented in Python (version 3.9. and the GNN model is designed and trained with Pytorch [22) (version 1.8.0) and pyG 23 (version 2.0.4). To train the GNN model, we build a dataset including 50,000 CDFGs. The operations in the CDFGs are annotated with the priorities solved by the Ibsed method (as introduced in Section 4.3). For efficiency, Gurobi [24] adopted as the II. solver. Details of dataset preparation are presented in supplementary materials. We conduct all the experiments
Ubuntu 20.04 LTS Linux Server with CPU (Intel(R) Xeon(R) Gold 5218 C 2.30GHz) and a GPU (NVIDIA Tesla V100). The experiments are conducted to answer the following questions:

---

Table I: Results of NeuroSchedule.
Testcase
CDFG
NeuroSchedule
Entropy-directed
I.P-hdded
Result
Dataset
Name
Basic Block
Node
Edge
Cycle
Time
Cycle
Time
Cycle
Time
5
Imp.
CHStone
adpem
main
0.019
0.004
52
2.842
0.00%
3.70%
CSSooe
ARK InvCol
79
192
0.013
77
0.005
77
2,430
0.00%
0.00%%
C CSSione
blowfish
BF set key
147
456
80
0.107
81
0.010
80
14.67
0.00%
1.23%
Clooo
dladd
R.PPFlau144
92
238
49
0.013
50
0.005
48
3.570
2.04%
2.00%
CHStone
didiv
Beaa64__div div
433
1252
235
0.060
256
0.027
N/A
>10
8.20%
CHStone
Roat64, mul
339
0.115
0.019
N/A
>10
7.25%
CHStone
Boui64 div
1187
0.063
0.026
N/A
9.38%
CHStone
main
68
148
41
0.029
41
0.003
40
2.121
2,445
0.00%
CSStone
Jpeg
write4Blocks
213
692
127
0.022
132
0.014
N/A
>10
3.79%
ClSooe
mips
main
364
1433
200
0.038
200
0.025
200
2207
0.00%
0.00M8
CHSSone
motion
ml. Vectors
0.010
0.003
0.509
0.00%
12.5%
CHStone
linal
79
202
0.012
0.004
49
4.141
0.00%
10.9%
MiBench
cosinel
cosinel
66
76
43
0.025
44
0.006
43
41.95
0.00%
2.27%
MiRench
ersine2
oosine?
0.100
0.003
57
11.07
0.00%
1.72%
MiBench
lirl
44
43
0.098
0.002
34
1.244
0.00%
0.00%
Millnch
fir2
fir2
40
39
31
0.028
32
0.002
31
1.478
0.00%
3.13%
MiBench
idcicol
dig_3
114
164
69
0.103
69
0.004
69
16.22
0.00%
0.005
MiBench
bmp_7 7
202
0.097
0.004
68
3.759
0.00%
1.45%
Total
2761
7448
1621
0.952
1699
0.167
>5 10*
Optimal Rate
88.89%
16.67%
N/A
Average Improvementt
0.30%
6.10%
6 (NeuroSchedale- - ILP.
Improvement (EDS NeurnSchedulle) EDS.
Average Improvement = (E NeunoSeeuuShhhccelle Σ (Cyel_JLLP)).. E Cycle_ILP. The optimal solutions (Imp. = 0.00%) are not counted in.
Q1: Could NeuroSchedule obtain better solutions than the entropy-directo
algorithm?
Q2: Could NeuroSchedule obtain optimal solutions with respect to the ILP-based method?
Q3: How fast is the proposed algorithm compared against the ILP-based method?
Q4: How do the pre-training methods work in enhancing the algorithm's scalability?
Q5: What are the differences between different loss functions?
6.1 Quality of Solutions
To answer Q1, evaluate the performance of NeuroSchedule against state-of-the-ar entropy- directed scheduling algorithm [13] and ILP-based method [I0] using the benchmarks from CH- Stone [25] and MiBench (26). The experimental results are presented in Table As shown in the table, NeuroSchedule improves the scheduling results by 6. 6.10% on average compared with EDS. Moreover, compared with the ILPedased method, NeuroSchedule obtains optimal solutions in 88.89% of the benchmarks and mear-optimal solutions in the rest, while EDS can only obtain 16.67% optimal solutions in all benchmarks.
To answer Q2, we synthesize a benchmark suite including large CDFGs with complex dependencies among the operations. The entangled dependencies make it hard for scheduling algorithms to find an optimal solution. We evaluate NeruoSchedule, entropy-directed algorithm [13] and ILP-based algorithm [0] on the synthesized complex benchmark suite. The results are presented in Figure 6 TigureBggive giiees the heatmaps for comparing the scheduling results among NeuroSchedule, entropy- directed algorithm, and ILP-based algorithm. As shown in Figure 6 bia,, NeuroSchedule obtains optimal solutions on 90% of the synthesized complex benchmarks. While in Figure b(b). the entropy- directed algorithm fails to obtain optimal solutions all of the benchmarks due to the complex operation dependencies. Moreover, as shown in Figure c), NeuroSchedule obtains better solutions on 94% of the synthesized complex benchmarks compared with the entropy-directed algorithm.
6.2 Execution Time
To answer Q3, we evaluate the runtime of NeuroSchedule against state-of-the-art entropy-directed scheduling algorithm and ILP-based method [10] using benchmarks from CHStone 225 and MiBench [26]. The results are presented in Table I As shown in the table, NeuroSchedule achieves more than 50,000x speedup compared with the P---dd method, while obtaining near-optimal solutions. Moreover, the II.P-baser method fails to solve certain benchmarks within 10,000 seconds due the exponential runtime overhead. Besides, since NeuroSchedule needs to launch CUDA kernels to compute operation priorities, it runs little slower than the intropy-directo algorithm.
8

---

1.05
(a)
(c)
Figure 6: Evaluations synthesized complex benchmark suite. The values in the heatmaps represent the relative scheduling results between different algorithms. (a) NeuroSchedule relative to ILP-basce algorithm. (b) catropy-directio algorithm relative ILP-based algorithm. (c) Entropy- algorithm relative to NeuroSchedule.
8.85
8.85
0..80
0..55
Optinal
0.75-
8.78
0.65
from-scratch
0.60
MSE Loss
fine-tune
0.55
Rank Loss
0.60
0.50
10
Epoch
Epoch (b)
Figure 7: Optimal rate curve during training. Optimal rate indicates the number of benchmarks in the synthesized suite with optimal solutions obtained by NeuroSchedule. (a) Fine-tuning method
compared against training from scratch. (b) Training with rank loss function compared against training with MSE loss function.
Nevertheless, NeuroSchedule is still fast and the difference runtime between NeuroSchedule and cntropy-directer algorithm could be ignored.
6.3 Pre-training and Fine-tuning
To answer Q4, we synthesize a small dataset that consists of 1000 CDFGs. Details the small dataset presented in supplementary materials. Based the synthesized small dataset, NeuroSchedule is trained in two different ways: from scratch and fined-tuned from the pre- teeitraining model. The synthesized benchmark suite in Section 6.1 is adopted to evaluate the two models trained in different ways. Besides, the optimal rate is selected as the metric, which indicates the number of benchmarks in the synthesized suite with optimal solutions obtained by NeuroSchedule. Figure 7 depicts the optimal rate curve during training. As shown in the figure, NeuroSchedule fine-tuned from the pre-training model achieves 3% improvement in the optimal scratch. Moreover, NeuroSchedule fine-tuned from the pre-training model achieves a better optimal rate while costing reduced training efforts compared with that trained from seratch.
compared with that trained from
6.4 Training Settings
To answer QS, NeuroSchedule is trained with MSE loss and Rank loss [21] on the synthesized small dataset described in Section The synthesized benchmark suite in Section 6..1 adopted to evaluate the two models trained with different loss functions. Besides, the optimal rate is selected the metric. Figure depicts the optimal curves during training. As shown in the figure, rank loss behaves slightly better than MSE loss, which indicates that training model for predicting the absolute value requires more effort than training model for predicting the rank. Therefore, the rank loss is chosen as the default training objective function.
7
Conclusion
This paper presents NeuroSchedule, a novel and effective GNN-based scheduling method for HL.S. NeuroSchedule learns predict operation priorities using GNN models. The predicted priorities are adopted list scheduling process. Besides, to enhance NeuroSchedule's scalability for various scheduling problems with different settings, pre-training methods are adopted. Experimental results

---

indicate that NeuroSchedule achieves significantly enhanced solutions compared with the state-of- the-art method. Moreover, NeuroSchedule obtains near-optimal solutions while achieving more than 50,000x speedup compared with the II.P-aseed algorithm. Future work includes elaborations on the training details for better tuning, supporting operation chaining, and testing of NeuroSchedule on larger and more complicated benchmarks.
Acknowledgments and Disclosure of Funding
This work was supported part by the Key R&D Program of China (No. 20900222020000) the Key Program of NSFC (No. 62034005), the NSFC (No. 61974084), and Beijing Municipal Science Technology Commission (No. 219110000511911),
References
[1] Xiaofan Zhang, Hanchen Ye, Junsong Wang, Yonghua Lin, Jinjun Xiong, Wen-Mei Hwu, and Deming Chen. Dnnexplorer: A framework for modeling and exploring a novel paradigm of fpga-based DNN accelerator. In TEEE/ACM International Conference On Computer Aided Design, ICCAD 2020, San Diego, CA, USA, November 2-5, 2020, pages 61:1-6133 IEEE, 2020.
[2] Song Han, Junlong Kang, Huizi Mao. Yiming Hu, Xin Li, Yubin Li, Dongliang Xie, Hong Luo, Song Yao. Yu Wang, Huazhong Yang, and William (Bill) J. Dally. ESE: efficient speech recognition engine with sparse LSTM on FPGA. In Jonathan W. Greene and Jason Helge Anderson, editors, Proceedings of the 2017 ACM/SIGDA International Symposium on Field- Programmable Gate Arrays, FPGA 2017, Monterey, CA, USA, February 22-24, 2017, pages 75 84. ACM, 2017.
[3] Xiaofan Zhang, Anand Ramachandran, Chuanhao Zhuge, Di He, Wei Zuo, Zuofu Cheng, Kyle Rupnow, and Deming Chen. Machine learning on fpgas to face the iot revolution. In Sri Parameswaran, editor, 2017 IEEE/ACM International Conference on Computer-Aide -ided Design, ICCAD 2017, Irvine, CA, USA, November 13-16, 2017, pages 819-820 826. IEEE, 2017.
[4] Suhaib A. Fahmy, Kizheppatt Vipin, and Shanker Shreejith. Virtualized FPGA accelerators for efficient cloud computing. In 7th IEFE International Conference on Cloud Computing Technology and Science, CloudCom 2015, Vancouver, BC, Canada, November 30 December 3, 2015, pages 430-435 IEEE Computer Society, 2015.
[5] Shaojie Xiang, Yi-Hsiang Lai, Yuan Zhou, Hongzheng Chen, Niansong Zhang, Debjit Pal, and Zhiru Zhang. Heteroflow: An accelerator programming model with decoupled data placement for software-defined fpgas. In Michael Adler and Paolo lenne, editors, FPGA '22: The 2022 eCM/SIGDA International Symposium on Wheld-Programmabbe Gate Arrays, Virtual Event, USA, 27 February 2022 March 2022, pages 78-88. ACM, 2022.
[6] Jennifer Pearl Smith, John I. Bailey III, John Tuthill, Leandro Stefanazzi, Gustavo Cancelo, Ken Treptow, and Benjamin A. Mazin. A tigh-throughput oversampled polyphase filter bank using vivado HLS and PYNQ on a rfsoc. IEEE Open J. Circuits Syst., 2:241-252, 2021.
[7] Andrew Canis, Jongsok Choi, Mark Aldham, Victor Zhang, Ahmed Kammoona, Jason Helge Anderson, Stephen Dean Brown, and Tomasz S. Czajkowski. Legup: high-level synthesis for fpga-based processorlacceleratoo systems. In John Wawrzynek and Katherine Compton, editors, Proceedings of the ACM/SIGDA 19th International Symposium Field Programmable Gate Arrays, FPGA 2011, Monterey, California, USA, February 27, March 1, 2011, pages 33-36. ACM, 2011.
[8] Fabrizio Ferrandi, Vito Giovanni Castellana, Serena Curzel, Pietro Fezzardi, Michele Fiorito, Marco Lattuada, Marco Minutoli, Christian Pilato, and Antonino Tumeo. Invited: Bambu: an open-source research framework for the high-level synthesis of complex applications. In 58th ACM/IEEE Design Automation Conference, DAC 2021, San Francisco, CA, USA, December 5-9, 2021, pages 1327-1330. IEEE, 2021.
[9] Jan Karel Lenstra, David B. Shmoys, and Êva Tardos. Approximation algorithms for scheduling unrelated parallel machines. Math. Program., 46:259-271, 1990.
10

---

[10] Cheng- Tsung Hwang, Jiahn-Human Lee. and Yu-Chin Hsu. A formal approach to the schedul- ing problem in high level synthesis. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 10(4):464 475, 1991.
[11] Alice C. Parker, Jorge T. Pizarro, and Mitch J. Mlinar. MAHA: a program for datapath synthesis. In Don Thomas, editor, Pruceedings of the 23rd ACM/IEEE Design Automation Conference. Las Vegas, NV, USA, June, 1986, pages 461-466. IEEE Computer Society Press, 1986.
[12] Pierre G. Paulin and John P. Knight. Force-directed scheduling for the behavioral synthesis of asics. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 8(6):661 1989.
[13] Minghua Shen, Hongzheng Chen, and Nong Xiao. Entropy-directed scheduling for FPGA high-level synthesis. IEEE Trans. Comput, Aided Des. Integr. Circuits Syst., 39(10):2588-261 2020.
[14] Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefamie Jegelka. How powerful are graph neural networks? In 7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019. OpenReview.net, 2019.
[15] Petar Velickovic, Guillem Cucurull, Arantxa Casanova, Adriana Romero, Pietro Liò, and Yoshua Bengio. Graph attention networks. In 6th International Conference Learning Representations ICLR 2018, Vancouver, BC, Canada, April 30 May 3, 2018, Conference Track Proceedings. OpenReview.net, 2018
[16] Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings. OpenReview.net, 2017.
[17] Zeyang Zhang, Ziwei Zhang, Xin Wang, and Wenwu Zhu. Learning to solve travelling salesman problem with hardness adaptive Intelligence, AAAI 2022, Thirty-Fourth Conference on Innovative Applications of Artificial Intel- ligence, IAAI 2022, The Twelveth Symposium on Educational Advances in Artificial Intelligence, FAAI 2022 Virtual Event, February 22- March 1, 2022, pages 9136-9144. AAAI Press, 2022.
hardness-adaptive curriculum. In Thirty-Sixth AAAI Conference on Artificial
[18] Chris Cummins, Zacharias V. Fisches, Tal Ben-Nun, Torsten Hoefler, Michael P. O' Boyle, and Hugh Leather. Programl: A graph-based program representation for data flow analysis and compiler optimizations. Marina Meila and Tong Zhang, editors, Proceedings of the 38th International Conference on Machine Learning, ICML 2021, 18-24 July 2021, Virtual Event, volume 139 of Proceedings of Machine Learning Research, pages 2244-2253 PMLR, 2021.
[19] Abien Fred Agarap. Deep learning using rectified linear units (relu). CoRR, fbs/1803.00875. 2018.
[20] Tianqi Chen, Lianmin Zheng, Eddic Q Yan, Ziheng Jiang, Thierry Moreau, Luis Ceze, Carlos Guestrin, and Arvind Krishnamurthy. Learning to optimize tensor programs. In Samy Bengio, Hanna M. Wallach, Hugo Larochelle, Kristen Grauman, Nicolò Cesa- Mosa-Bianchi, and Roman Garnett, editors, Advances in Neural Information Processing Systems 31: Annual Conference on Neural Information Processing Systems 2018, NeurlPS 2018, December 3-8, 2018, Montréal, Canada, pages 3393-3404, 2018.
[21] Christopher J. C. Burges, Tal Shaked, Erin Renshaw, Ari Lazier, Matt Deeds, Nicole Hamilton, and Gregory N. Hullender. Learning rank using gradient descent. In Luc De Raedt and Stefan Wrobel, editors, Machine Learning, Proceedings of the Twenty-Second International Conference (ICML 2005). Bonn, Germany, August 7-11, 2005, volume 119 of ACM International Conference Proceeding Series, pages 89-96. ACM, 2005.
[22] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward Z. Yang, Zachary Vito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high-performance deep learning library. In Hanna M. Wallach, Hugo Larochelle, Alina Beygelz- imer, Florence d' Alché-Bun Buc, Emily B. Fox, and Roman Garnett, editors, Advances Neural Information Processing Systems 32: Annual Conference Neural Information Processing
11

---

Systems 2019, NeurlPS 2019, December 8-14, 2019, Vanconver, BC, Canada, pages 2019.
[23] Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. CoRR, abs/1903.02428, 2019.
[24] Gurobi Optimization, LLC. Gurobi Optimizer Reference Manual, 2022.
[25] Yuko Hara, Hiroyuki Tomiyama, Shinya Honda, Hiroaki Takada, and Katsuya Ishii. Chstone: A henchmark program suite for practical c-based high-level synthesis. In International Symposium on Circuits and Systems (ISCAS 2008). 18-21 May 2008, Sheraton Seattle Hotel, Seattle, Washington, USA, pages 1192-1195. IEEE, 2008.
[26] Matthew R Guthaus, Jeffrey S Ringenberg, Dan Ernst, Todd M Austin, Trevor Mudge, and Richard Brown. Mibench: free, commercially representative embedded benchmark suite. In Proceedings of the fourth annual IEEE international workshop on workload characterization. WWC-4 (Cat, No. 01 EX538), pages 14. IEEE, 2001.
12

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes] See Section and Section 7
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you experiments..
(a) Did you include the code. data, and instructions needed reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [No] Our Neu- roSchedule will be open-soureed once the paper is accepted.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] See Section 4 and the supplementary materials.
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [No]
(d) Did you include the total amount of compute and the type of resources used (c.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any assets either in the supplemental material URL? [Yes]
We put the large CDFG dataset into our supplementary materials.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [Yes] The benchmarks used in our paper are open-sourced, and cite them in our paper.
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
13


Reviews:
[{"review_id": "anbF_Grqbj", "reviewer": "Reviewer_tUpk", "summary": "This paper proposes NeuroSchedule, a GNN-based scheduling method for HLS. At the core of NeuroSchedule is a novel priority function that predicts the priority (rank) of a ready operation, which is used for list scheduling. To improve the scalability of NeuroSchedule over different settings, pre-training methods are adopted, which can be fine-tuned for downstream tasks. NeuroSchedule effectively approximates the optimal ILP-based priority function at a 50,000x lower computation cost. This leads to an average of 6.10% improvement in cycles over the Entropy-Directed Scheduling (EDS) algorithm.", "questions": "* How would NeuroSchedule handle more complex/realistic applications with non-deterministic events such as DRAM accesses, caching, bank conflicts, etc?\n\n* In Equation (2), why ALAP includes the second definition with ASAP() for those vertices not connected to $v_i$? Can you elaborate on this?", "limitations": "I find this paper presents an interesting proposal and was a very enjoyable read. As far as I know, this is the first work that formulates the scheduling priority function as a learning task with GNN to effectively approximate the optimal ILP algorithm at a tiny fraction of computation cost. Indeed, it's a promising direction and the results demonstrate the effectiveness of the proposed idea.\n\nWhile I like the direction of this work, my acceptance is *weak* for the following limitations. For benchmark selection, most of the benchmarks look pretty small in scale, taking tens of cycles in most cases. At this point, it is not clear how effective NeuroSchedule would be for more realistic/complex applications that may require off-chip DRAM accesses, caches, and other non-deterministic behaviors. Also, while delivering competitive results to the optimal ILP-based schedule in most cases, the average improvement over EDS is rather small. This makes me question about the practical value of NeuroSchedule as its average improvement over EDS would go below 5% if we include those optimal benchmarks omitted while it takes about 6$\\times$ longer scheduling time.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Strengths**\n\n* The approach of applying GNN to HLS scheduling is novel and clever.\n\n* NeuroSchedule demonstrates competitive results to the optimal ILP algorithm at a tiny faction of computation cost.\n  \n\n**Weaknesses**\n\n* The effectiveness of NeuroSchedule is demonstrated only for small-scale kernel benchmarks taking just tens of cycles in most cases.\n\n* The relatively small average improvement over EDS (i.e., 6.10% *without* including those with 0.0% improvement) while taking some 6$\\times$ longer to run.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "agfYioCnOXD", "reviewer": "Reviewer_PRGS", "summary": "This paper implements a task scheduler for HLS based on the GNN model, and the suitable method for HLS scheduling is proposed for the first time. In hardware programming, it is necessary to convert a high-level language into a circuit-level implementation, but this step is time-consuming and yields poor quality in traditional methods. According to the characteristics of many data dependencies in the generation of CDFG during the compilation process, combined with the GNN model that can perform well on complex graphs, the proposed scheduling method can speed up the execution time of the synthesis step and improve the quality of the generated circuit-level language.", "questions": "1. It is not clear enough at Equations (1) & (2), considering that priority determination is the key to scheduling steps, more details need to explain ASAP/ALAP?\n2. In line 138 the author indicates that the smaller value the higher priority is, but in line 140 it indicates the algorithm schedules the largest value, the description here is confusing.\n3. The description of the encoding operator in line 181 is not clear, and further normalized features can reduce the impact of noises, which is not well explained in the paper.\n4. In Section 5.2, it is mentioned that V_chosen on line 25 of the algorithm, but the algorithm has only 23 lines, which makes it difficult to understand.\n5. What is the final time interval for different scheduling sequences in Figure 5 (b) and (c)? This supplement would give a intuitive explanation on the operation’s flexibility during scheduling.\n", "limitations": "yes", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths\n1. The paper gives a clear example to illustrate the targeted optimization algorithm, which can clearly explain the purpose of this article, and the writing logic is clear, the motivation and optimization point of this paper is clearly clarified.\n2. It converts the overall priority to a relative order that is more convenient for calculation when performing operations, thereby reducing the complexity of the overall calculation.\n3. The application scenario is consistent with GNN, and the priority of each operator is predicted through the GNN model, thereby reducing the execution time of the entire process.\n\nWeaknesses\n1. Some descriptions need to be more detailed. For example, when it is stated in the Introduction that operators of the same type in each step are mutually exclusive, a restrictive description of the execution should be given to avoid readers' guessing.\n2. NeuroSchedule introduces GPU for calculation. The experimental results only compare the accuracy with the EDS method (in Section 6.1), emphasizing the improvement of the accuracy, and the final execution time is longer than that of EDS. The paper lacks the analysis of the benefit ratio of additional computing device.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "D8ZO1TP_Z1E", "reviewer": "Reviewer_2hWG", "summary": "The authors propose NeuroSchedule, a GNN-based schedule for solving the high-level synthesis (HLS) problem in the FPGA development. NeuroSchedule is the first GNN-based scheduler in this domain. It is trained using supervised learning with data labeled by the ILP-based scheduler. NeuroSchedule has an extremely good runtime improvement over the ILP-based scheduler, while achieving near-optimal solutions. NeuroSchedule is also compared with a heuristic-based method. Its run-time is not as good as the heuristic method, but its solutions are generally better. ", "questions": "-\tShould “max” in Line 41 be “min”, since the list scheduling algorithm picks the operations with the highest priority first and smaller F values indicate higher priorities?", "limitations": "The experiment shows the proposed method is slower than the heuristic entropy-directed method.\n\nIt would be better to mention how long it took to label the training data set of 50,000 CDFGs by the ILP-based scheduler. Not necessary a limitation, but the readers may want to know.\n\n", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n-\tThe inference time of the proposed algorithm is 50,000 times faster than its teacher schedule (ILP-based optimizer).\n-\tThe quality of solutions provided by NeuroSchedule are better than the state-of-the-art entropy-directed method by 6.10% on average.\n-\tBy fine-tuning the pre-trained model, NeuroSchedule can get good results in different settings.\n-\tThe rank-loss (relative priorities) helps the trained model to get a better optimal rate, compared with traditional MSE loss.\n-\tThe experiment section is well organized. \n\nWeaknesses:\n\n-\tIt would be better to conduct significant test to see whether the performance of NeuroSchedule is significantly better than the entropy-directed method.\n-\tIt would be better to compare with some reinforcement learning based scheduling methods.\n-\tThere may be a typo in one of the formulas. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "AbQa2-2Y2vw", "reviewer": "Reviewer_1vbZ", "summary": "This paper proposes NeuroSchedule, an efficient and effective GNN-based scheduling method designed for the HLS. This paper formulate the learning problem of the operation scheduling in HLS and is able to embed the operation information in the GNN to aid learning the schedule. This paper further builds a dataset of CDFGs with different scheduling settings to pre-train the model. With final-tuning on randomly generated designs in different settings, the model's prediction is able to be generalized.", "questions": "1. HLS seems to be not that related in this article. This article seems more about the general operation scheduling. Is there any special reason or limitation why the authors decide the scope of HLS?\n2. How do the authors solve the case of resource conflict, if the hardware modules are to be reused? Not only the operation dependency will influence the scheduling, whether the hardware module busy or not will also have impact. For instance in Fig5.a, what if there are some restrictions that the first two addition have to use the same adder\n3. Will and how do the authors consider HLS's different pargmas in the scheduling, as they will decently impact the scheduled performance via changing the underlying hardware, such as buffer memory size/bandwidths?\n", "limitations": "Yes, it's addressed.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n1. This paper proposes a formulated and more likely to be standardized method to solve the seemingly intractable scheduling problem in HLS. This may open door and inspire more ML techniques to be effectively applied in the hardware design.\n2. The methodology description along with the supplementary material is clear and easy for the readers to follow or potentially reproduce\n\nWeakness:\n1. The results' improvements are hard to be justified as significant, compromising the method's effectiveness: As shown in Table 1, as compared with Entropy-directed methods, overall the runtime latency is improved by 16.67% but the optimization run-time is 5.7 times more. Further compare with the eligible options in ILP-based, it is shown that Entropy-directed method is already near optimal. Then it is questionable if it is worth it for the relatively small latency improvement but with huge degradation on the scheduling run-time.\n2. A little too simplified scheduling assumption based mainly on individual operation latency and dependency, but authors can clarify in the following questions to clear the concern.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept