# Lightweight 1-D CNN-based Timing Synchronization for OFDM Systems
with CIR Uncertainty

Chaojin Qing, Shuhai Tang, Xi Cai, and Jiafan Wang This work is supported in
part by the Sichuan Science and Technology Program (Grant No. 2021JDRC0003),
the Major Special Funds of Science and Technology of Sichuan Science and
Technology Plan Project (Grant No. 19ZDZX0016 /2019YFG0395), the Special Funds
of Industry Development of Sichuan Province (Grant No. 2020-YF09- 00048-SN),
and the Demonstration Project of Chengdu Major Science and Technology
Application (Grant No. zyf-2018-056).C. Qing, S. Tang, X. Cai, and J. Wang are
with the School of Electrical Engineering and Electronic Information, Xihua
University, Chengdu, 610039, China (E-mails<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>and jifanw@gmail.com).

###### Abstract

In this letter, a lightweight one-dimensional convolutional neural network
(1-D CNN)-based timing synchronization (TS) method is proposed to reduce the
computational complexity and processing delay and hold the timing accuracy in
orthogonal frequency division multiplexing (OFDM) systems. Specifically, the
TS task is first transformed into a deep learning (DL)-based classification
task, and then three iterations of the compressed sensing (CS)-based TS
strategy are simplified to form a lightweight network, whose CNN layers are
specially designed to highlight the classification features. Besides, to
enhance the generalization performance of the proposed method against the
channel impulse responses (CIR) uncertainty, the relaxed restriction for
propagation delay is exploited to augment the completeness of training data.
Numerical results reflect that the proposed 1-D CNN-based TS method
effectively improves the TS accuracy, reduces the computational complexity and
processing delay, and possesses a good generalization performance against the
CIR uncertainty. The source codes of the proposed method are available at
https://github.com/qingchj851/CNNTS.

###### Index Terms:

Timing synchronization (TS), orthogonal frequency division multiplexing
(OFDM), deep learning (DL), relaxed restriction for propagation delay.

##  I Introduction

Orthogonal frequency division multiplexing (OFDM) has been adopted in many
standards[1], such as the IEEE 802.11a/n standards, the Internet-of-Things
(IoT), and the fifth generation (5G), due to its high spectral efficiency
whilst providing resilience to frequency-selective fading [2]. In OFDM
systems, timing synchronization (TS) plays a key role[1] in the subsequent
channel estimation [3] and symbol detection[4]. Hence, a variety of classic TS
methods have been developed for OFDM systems, e.g., the auto-correlation-based
TS [5, 6, 7] and the cross correlation-based TS [8, 9]. However, these classic
methods in[5, 6, 7, 8, 9] inevitably encounter nonlinear effects, e.g., multi-
path interference, which pose a great challenge to improve the accuracy of TS.

To enhance these classic TSs, extreme learning machine (ELM)-based approaches
were proposed in [10, 11, 12]. In [10], an ELM-based method was proposed to
estimate the residual timing offset (TO), in which the coarse TS was assumed
to have been accomplished. In [11] and [12], the ELM networks were employed to
refine the TS with preprocessing approaches based on the auto-correlation and
cross-correlation, respectively. Although the performance of classic TSs is
enhanced by using ELM in [10, 11, 12] (especially for the scenarios with
nonlinear effects in [10, 12]), several important issues have not been well
addressed. Firstly, the ELM network is a single hidden layer-based feed-
forward network which leads to limited learning ability. It motivates us to
develop a deep learning (DL) network to further enhance the TS accuracy while
alleviating substantially computational complexity and processing delay caused
by the requirement of preprocessing in [10, 11, 12]. Secondly, the ELMs in
[10, 11, 12] can be viewed as denoising networks, and the powerful ability of
artificial neural network (ANN) has not been well developed, e.g., the feature
extraction of TS for OFDM. Finally, these TSs in [10, 11, 12] are
significantly affected by the uncertainty of the power delay profile (PDP) of
multi-path channels (or channel impulse response (CIR) uncertainty), due to
the fact that the first arriving path is not always the strongest. For
example, the efficiency of feature extraction is hindered by using the auto-
correlation and cross-correlation as preprocessing, and this degrades the
learning ability of ELM-based approaches for the TS in OFDM systems.

Recently, the method to locate the first arriving path is recalled in [13] by
employing compressed sensing (CS), yet the advantages of ANN were not
exploited and the high computational complexity of iteration reconstruction
hinders its application. To this end, a high-accuracy ANN-based TS is highly
desired to improve the ELM- and CS-based TSs for OFDM systems with a tolerable
computational complexity and processing delay in the scenarios of the CIR
uncertainty.

To circumvent the above issues, we propose a lightweight one-dimensional
convolutional neural network (1-D CNN)-based TS, in which a relaxed
restriction of propagation delay would alleviate the CIR uncertainty. To the
best of our knowledge, the application of the 1-D CNN and the relaxed
restriction of propagation delay is limited, while our solution fills this gap
by improving the TS accuracy against the CIR uncertainty with the reduced
computational complexity and processing delay (i.e., network lightweight). The
main contributions are summarized as follows:

  * •

We propose a 1-D CNN-based method to improve the TS accuracy from the
perspective of classification tasks. In this developed method, the TS is
transformed into a DL-based classification problem. In particular, the
advantage of CNN in performing the feature extraction is exploited, and thus
highlights its classification features for TS. Compared with TS methods in
[11, 10, 12], the TS accuracy is significantly improved.

  * •

We develop a lightweight NN structure to reduce the processing delay and
computational complexity. Especially, the CNN architecture is simplified by
unfolding a few iterations of CS-based TS in [13]. Besides, the dedicated
filter size and filter number of each CNN layer are designed to highlight the
classification features (from the receptive fields of TS features) without
increasing the parameters of the network. In this way, features of the
training sequence are effectively extracted with a relatively low processing
delay and computational complexity.

  * •

We exploit the relaxed restriction of propagation delay to augment the
completeness of training data for alleviating the CIR uncertainty.
Particularly, a propagation delay that is greater than the real one and a
random PDP are exploited to increase the completeness of training data. This
relaxed method improves the generalization performance of the proposed 1-D
CNN-based TS against the CIR uncertainty, and thus possesses a good
generalization capacity compared with those TS methods in [11, 10, 12].

Notations: The notations adopted in this letter are described as follows.
$\mathbb{R}^{M\times N}$ and $\mathbb{C}^{M\times N}$ stand for the $M$-by-$N$
dimensional real matrix space and $M$-by-$N$ dimensional complex matrix space,
respectively. $[\cdot]^{T}$, $\mathrm{E}\\{\cdot\\}$, $|\cdot|$,
$\lceil\cdot\rceil$, and $\lfloor\cdot\rfloor$stand for the transpose
operation, expectation operation, absolute operation, ceiling function, and
floor function, respectively. $[\mathbf{X}]_{m,n}$ denotes the entry $(m,n)$
of matrix $\mathbf{X}$, respectively. $\Re(x)$ and $\Im(x)$ denote the real
and imaginary parts of value $x$, respectively.

Figure 1: System model and 1-D CNN-based timing synchronizer.

##  II System Model

The system model is given in Fig. 1, in which the OFDM modulation is employed.
In the frequency domain, the data symbol $d_{k}$, with $0\leq k\leq N-1$ and
$N$ being the number of sub-carriers, is transformed to the time domain by
using inverse discrete Fourier transform (IDFT), and its $n$-th sample
(denoted as $s_{n}$) is given by

${s_{n}}=\frac{1}{{N}}\sum\limits_{k=0}^{N-1}{{d_{k}}\exp\left(j2\pi{\frac{{kn}}{N}}\right)},$
(1)

where $s_{n}$ satisfies that $\mathrm{E}\\{|s_{n}|^{2}\\}=\sigma^{2}_{d}$,
with $\sigma^{2}_{d}$ being transmitted signal power. After appending the
$L_{c}$-length cyclic prefix (CP) and transmitting OFDM signals over the
wireless channel[14], the $n$th sample of received signal is expressed as:

${r_{n}}=\sum\limits_{p=1}^{P}{{h_{{\tau}_{p}}}{s_{n-\widetilde{\tau}-{\tau}_{p}}}}\exp\left({j2\pi\varepsilon\frac{{{n-\widetilde{\tau}}}}{N}}\right)+{w_{n}},$
(2)

where $P$, $h_{{\tau}_{p}}$, $\widetilde{\tau}$, ${{\tau}_{p}}$, and
$\varepsilon$ separately stand for the number of resolvable multi-path, the
channel complex gain of $p$-th path, the unknown TO to be estimated, the delay
of $p$-th path relative to the first arriving path, and carrier frequency
offset (CFO). $w_{n}$ denotes the circularly symmetric complex Gaussian noise,
i.e., ${w_{n}}\sim\mathcal{CN}(0,\sigma^{2}_{n})$ with $\sigma^{2}_{n}$ being
the noise power. By extracting the real and imaginary parts of the $M$-length
received signal, the input of 1-D CNN-based timing synchronizer, i.e,
$\textbf{y}\in\mathbb{R}^{2M\times 1}$ in Fig. 1, is formed as

${\bf{y}}={\left[{\Re(r_{0}),\Im(r_{0}),\cdots,\Re(r_{M-1}),\Im(r_{M-1})}\right]^{T}},$
(3)

where $M$ ($M=N_{u}+N$) is the length of observation interval and
$N_{u}=N+L_{c}$. In this letter, we design a lightweight DL-based timing
synchronizer to estimate the TO $\widetilde{\tau}$ against the CIR
uncertainty.

##  III 1-D CNN-based Timing Synchronizer

In this section, the proposed 1-D CNN-based TS for OFDM systems is elaborated.
In Section III-A, the architecture of the proposed timing synchronizer is
characterized in detail and then followed by the relaxed restriction for
propagation delay in Section III-B. Next, Section III-C presents the offline
and online implementations. Finally, the computational complexity and
processing delay are given in Section III-D.

###  III-A Lightweight Network Architecture

To reduce the computational complexity and processing delay, a lightweight
network for TS is highly desired. To this end, we propose a 1-DCNN-based
timing synchronizer and make a dedicated design for its filter size. The
network architecture is summarized in Table I (its processing procedure is
presented in Fig. 1), and the detailed descriptions are given as follows.

This timing synchronizer consists of a three-layer 1-D CNN along with a
single-hidden-layer fully connected neural network (FCNN) layer. In the
proposed synchronizer, the first CNN layer is related to the processing of the
classic cross-correlation, and the second and the third CNN layers aim to
extract the significant features of the training sequence, followed by the
FCNN layer to make the final decision about the TO estimation. In these three
CNN layers, the valid padding and stride 2 are adopted for the first CNN layer
to reap the real and imaginary parts of $r_{n}$ given in (3), $0\leq n\leq
M-1$, while the same padding and stride 1 are applied for the rest CNN layers
to retain significant features. Each CNN layer is activated by a rectified
linear units (ReLU) activation function. For the FCNN layer, one hidden layer
and the tanh activation function are employed to fuse TS features. Between CNN
layers and the FCNN layer, an average pooling layer is utilized to reduce the
computational complexity. At the output layer, a softmax activation function
is adopted, and is followed by a linear classifier to produce the candidates
of TO.

TABLE I: Network Architecture of 1-D CNN-based Timing Synchronizer Layer Name | Size of output | Size of filter | Number of filter | Activation
---|---|---|---|---
Input Layer | $2M\times 1\times 1$ | - | - | -
CNN Layer 1 | $N_{u}\times 1\times 4$ | $(2N+1)\times 1$ | 4 | ReLU
CNN Layer 2 | $N_{u}\times 1\times 4$ | $(\lceil L_{c}/2\rceil+1)\times 1$ | 4 | ReLU
CNN Layer 3 | $N_{u}\times 1\times 2$ | $(\lceil L_{c}/2\rceil+1)\times 1$ | 2 | ReLU
Average pooling | $\lfloor N_{u}/2\rfloor\times 1\times 2$ | - | - | -
Flattening | $2\lfloor N_{u}/2\rfloor\times 1$ | - | - | -
FCNN Layer | $N_{u}\times 1$ | - | - | Tanh
Output Layer | $N_{u}\times 1$ | - | - | Softmax

######  Remark 1.

The lightweight network is mainly reflected in the three-layer 1-D CNN
architecture. Based on the model-driven mode, we unfold and simplify three
iterations of CS-based TS in [13] to form three simplified CNN layers (the
simplified details are given in Remark 3.). Since only three iterations are
unfolded and these iterations are simplified, the proposed method is extremely
lightweight, so that its computational complexity and processing delay are
significantly reduced compared with [13]. Besides, the 1-D CNN is developed
rather than the 2-D CNN (or FCNN), and the pooling layer is also employed,
leading to the network being lightweight as well.

######  Remark 2.

Usually, the TS accuracy is closely related to the timing metric (TM). In this
letter, we improve the TM by using a dedicated design of filter size. First,
the ($2N+1$)-length filter size is utilized to form a relatively large
receptive field for capturing the complete features of TM in the first CNN
layer. The main consideration is to involve the whole features of the training
sequence to replace and enhance the preprocessing of ELM-based TS in [10, 11,
12], e.g., the cross-correlation-based preprocessing in classic TSs. This is
different from the ELM-based TS in [10, 11, 12] since the preprocessing is not
adopted. Then, the relatively small filter size, i.e., $\lceil
L_{c}/2\rceil+1$ ($L_{c}$ denotes the length of CP), is developed for both the
second and third CNN layers to extract and refine the significant features of
TM. Due to the relatively small filter size, the processing delay and
computational complexity are reduced.

######  Remark 3.

For simplifying CNN layers, we also develop a relatively small number of
filters and make a trade-off among the three layers. In the first CNN layer,
four filters are adopted to maintain the complete features of TM, which are
held and highlighted by another four filters employed in the second CNN layer.
In the third CNN layer, we only use two filters to refine the significant
features of TM. By this means, high relevant features of the training sequence
are efficiently extracted, thus facilitates the subsequent classification in
the FCNN layer. Also, the number of filters in each CNN layer is small and the
convolutional process is the linear weighted sum of two 1-D data so that CNN
layer is simplified.

###  III-B Relaxed Restriction for Propagation Delay

Although the ELM-based TSs in [10, 11, 12] improve the TS accuracy of classic
TS methods to some extent, they inevitably encounter the CIR uncertainty. The
CIR uncertainty weakens the PDP correlation between the training CIRs and the
real ones, and thus degrades the learning efficiency of NN in ELM-based TS. To
tackle this challenge, we relax the restriction for PDP of CIRs by extending
its maximum propagation delay to augment the completeness of training data
(especially for the scenarios that have not been experienced). The received
power in the scenarios of line of sight (LOS) is
$P_{r}=\frac{\lambda^{2}}{(4\pi\zeta)^{2}}\sigma^{2}_{d}G_{t}G_{r}$ [15] with
$\lambda$, $\zeta$, $G_{t}$, and $G_{r}$ being the wavelength, propagation
distance, transmitted antenna gain, and received antenna gain, respectively.
Then, the maximum propagation delay $\tau_{P}$ in non-line-of-sight (NLOS)
scenarios is given by

$\tau_{P}=\frac{\zeta_{max}}{c}-|\Delta\tau|,$ (4)

where $c$ denotes the speed of light, $|\Delta\tau|$ is the delay fluctuation,
and $\zeta_{max}$ stands for the maximum propagation distance (resolvable
power $P_{r}$) with given transmitted power $\sigma^{2}_{d}$ in LOS scenarios.
We employ the maximum propagation distance ${\zeta_{max}}$ in LOS with given
$\sigma^{2}_{d}$ as the relaxed restriction for NLOS, since its propagation
distance is inevitably reduced by encountering obstacles. By denoting
$\tau_{\rm relax}$ as the relaxed restriction for propagation delay, we have

$\tau_{\rm relax}=\frac{\zeta_{max}}{c}={\tau_{P}}+|\Delta\tau|.$ (5)

With the relaxed restriction of propagation delay $\tau_{\rm relax}$, the
channel model that we employ to construct the training data set obeys the
exponentially decayed PDP [14] with its exponent ${\eta}$ satisfying
${\eta}\sim\mathcal{U}(0.01,0.5)$. Although the channels with exponentially
decayed PDP are employed for training, the trained network can effectively
work in most channel scenarios, e.g., the 5G channel models given in 3GPP TR
38.901 [16], possessing excellent generalization performance.

######  Remark 4.

According to the above $\tau_{\rm relax}$ and $\eta$, the completeness of
training data and the robustness of timing [11] have been improved. In other
words, a larger maximum multi-path delay and a random PDP may generate real
CIR profiles with higher probability, so that the generalization performance
of NN in our TS method is boosted against the CIR uncertainty.

###  III-C Offline Training and Online Deployment

The DL framework[17] named Keras functional API along with TensorFlow is
employed to implement the 1-D CNN-based timing synchronizer. The processes of
offline training and online deployment are given as follows, respectively.

####  III-C1 Offline Training

For training data, the relaxed restriction for propagation delay, i.e.,
$\tau_{\rm relax}$, and $\eta$ in Section III-B are employed. $N=128$
($L_{c}=N/4=32$ [18]) and $P=23$ [16] ($\tau_{P}$ uses $(P-1)$ sample
periods[19], i.e., $\tau_{P}=22$) are considered. The training data set
$\bm{\aleph}$ with $N_{t}$ ($N_{t}=10^{5}$) training samples is expressed as

${\bm{\aleph}}=\\{\mathbf{r}_{i},\mathbf{t}_{i}\\}^{N_{t}}_{i=1},$ (6)

where $\mathbf{r}_{i}\in\mathbb{C}^{M\times 1}$ is the training data with its
entries given in (2), and $\mathbf{t}_{i}\in\mathbb{R}^{N_{u}\times 1}$
denotes the corresponding TS label. According to the one-hot coding [11],
$\mathbf{t}_{i}$ is given by

$\small{{\bf{t}}_{i}}={\left[{\underbrace{0\cdots
0}_{\left\lceil{\widetilde{\tau}_{i}}+{\frac{1}{2}\left({{L_{c}}+{\tau_{{\rm{relax}}}}}\right)}\right\rceil}1\underbrace{0\cdots
0}_{{N_{u}}-\left\lceil{\widetilde{\tau}_{i}}+{\frac{1}{2}\left({{L_{c}}+{\tau_{{\rm{relax}}}}}\right)}\right\rceil-1}}\right]^{T}},$
(7)

where $\widetilde{\tau}_{i}$ is the TO of the $i$-th training
data,$\widetilde{\tau}_{i}\sim\mathcal{U}(0,N-1)$,
$\Delta\tau=\lceil(L_{c}-\tau_{P})/2\rceil=5$, and $\tau_{\rm
relax}=\tau_{P}+|\Delta\tau|=27$ sample periods according to (5) for the
offline training phase.

According to (3), the model input $\mathbf{y}_{i}\in\mathbb{R}^{2M\times 1}$
is obtained. Since the TS is transformed into the DL-based classification
problem, its model output $\mathbf{p}_{i}\in\mathbb{R}^{N_{u}\times 1}$
corresponds to the probability of candidate TO, which is given by

$p_{i,j}=\frac{\exp(o_{i,j})}{\sum\nolimits_{j=0}^{{N_{u}}-1}{\exp\left({{o_{i,j}}}\right)}},$
(8)

where $o_{i,j}=[\textbf{o}_{i}]_{j,1}$ and $p_{i,j}=[\textbf{p}_{i}]_{j,1}$,
with $\textbf{o}_{i}$ being the input of the last layer of FCNN, and
$\mathbf{p}_{i}$ being the output of FCNN.

The cross entropy ($\sum\nolimits_{j=0}^{{N_{u}}-1}{{t_{i,j}}\log{p_{i,j}}}$
with $t_{i,j}=[\mathbf{t}_{i}]_{j,1}$) is adopted as the loss function, in
which the stochastic gradient descent (SGD) with Adam optimizer is employed.
The optimizer parameters are set as $\alpha=0.001$, $\beta_{1}=0.9$, and
$\beta_{2}=0.999$[20]. During the training phase, the DL-based model $f_{m}$
is fitted with ${\bm{\aleph}}$, which is expressed as

${f_{m}}\leftarrow\mathrm{Train}{{}_{{f_{m}}}}\left({{\bm{\aleph}},{\bf{\Theta}},e}\right),$
(9)

where ${\bf\Theta}$ denotes the network parameters to be optimized, and $e$
represents the $e$-th training processes that contains the usual operations of
forward (back) propagation and weights update [20]. Since the TS is to locate
the TO in the ISI-free region, the trained network parameters is formulated as

${\bf\Theta}\leftarrow\mathop{\min}\limits_{{R_{\textrm{err},e}}}\\{\mathrm{Train}{{}_{{f_{m}}}}\left({{\bm{\aleph}},{\bf\Theta},e}\right)\\},$
(10)

where
$R_{\textrm{err},e}=[\sum\nolimits_{i=1}^{{N_{t}}}{{\theta\left(\widehat{\tau}_{i},\widetilde{\tau}_{i}\right)}}]/{{{N_{t}}}}$
is utilized to evaluate the accuracy of TS and save the best network
parameters after the $e$-th training process, and
$\theta\left({{\widehat{\tau_{i}}},{\widetilde{\tau}_{i}}}\right)$ is given by

$\theta\left({{\widehat{\tau_{i}}},{\widetilde{\tau}_{i}}}\right)=\left\\{\begin{array}[]{l}0,\
0\leq{\widetilde{\tau}_{i}}-{\widehat{\tau}_{i}}\leq
L_{c}-{\tau_{{\rm{relax}}}}\\\ 1,\ {\rm{others}}\end{array}\right.,$ (11)

where the estimated TO is expressed as

$\widehat{\tau_{i}}=\mathop{\arg\max}\limits_{0\leq
j\leq{N_{u}}-1}\\{p_{i,j}\\}.$ (12)

####  III-C2 Online Deployment

With the trained 1-D CNN-based timing synchronizer, its online running
performs as the TS for OFDM systems. By using (1)–(3), the model input of
timing synchronizer, i.e., $\mathbf{y}\in\mathbb{R}^{2M\times 1}$, is
obtained. With the input $\mathbf{y}$, $\\{p_{j}\\}^{N_{u}-1}_{j=0}$ is
produced, and thus the TO estimation is

$\widehat{\tau}=\mathop{\arg\max}\limits_{0\leq j\leq{N_{u}}-1}\\{p_{j}\\}.$
(13)

###  III-D Computational Complexity and Processing Delay

The computational complexity and processing delay among different methods for
TS are elaborated in Table II, in which the complex multiplication (CM) is
employed to as the metric of computational complexity. $N_{l}$ and $N_{l-1}$
denote the neuron numbers of the current and previous layers, respectively;
$K_{l}$ is the filter size of the $l$-th CNN layer; $C_{l}$ and $C_{l-1}$
represent the filter numbers of current and previous CNN layers, respectively;
$\mathcal{L}_{c}$ and $\mathcal{L}_{d}$ stand for the total layer numbers of
1-D CNN and FCNN layers, respectively. For the CS-based TS method in [13], the
constraint length orthogonal matching pursuit algorithm is employed as the
comparison. For a fair comparison, the complete synchronization process in
[13] is selected to compute its CMs and processing delays, since the method of
[13] cannot complete the TS without estimating or equalizing CIRs. Due to the
lightweight network architecture, the CM of the proposed method is
significantly lower than those of the CS- and ELM-based methods (in [11] and
[13], respectively). This is verified by the example given in Table II, where
$N=128$, $L_{c}=32$, $N_{u}=160$, and $P=28$ are considered. Meanwhile,
$10^{4}$ simulations are employed to evaluate the processing delay, and the
proposed 1-D CNN-based TS method reaps the smallest processing delay among
different TS methods. On the whole, compared with the CS and ELM-based TSs,
the proposed 1-D CNN-based TS reduces the processing delay and computational
complexity due to the lightweight NN architecture.

TABLE II: Computational Complexity and Processing Delay among Different TS Methods Method | Computational Complexity | CM | Time (sec)
---|---|---|---
CS [13] | $\mathcal{O}[PN{N_{u}}+\sum\nolimits_{p=1}^{P}({3p{N_{u}}}+{p^{3}}+{p^{2}}{N_{u}})]$ | $2167396$ | $81.41$
ELM [11] | $\mathcal{O}[\frac{3}{2}N+4(N_{u}-1)+16N_{u}^{2}]$ | $410428$ | $1.61$
Proposed | $\mathcal{O}[\frac{1}{4}(\sum\nolimits_{l=2}^{\mathcal{L}_{c}}{{N_{l}}{K_{l}}{C_{l}}{C_{l-1}}}+\sum\nolimits_{l=2}^{\mathcal{L}_{d}}{{N_{l}}{N_{l-1}}})]$ | ${70240}$ | $0.35$

Figure 2: The error probability of TS versus SNR.

##  IV Numerical Results

This section provides numerical results to evaluate the synchronization
performance. Basic parameters involved in the simulation are given as follows.
$N=128$, $L_{c}=N/4=32$[18], $N_{u}=N+L_{c}=160$, and $M=N_{u}+N=288$ are
considered. The transmitting training sequence for TS is the Zadoff-Chu
sequence[21]. For the convenience of expression, we leverage the “Prop”, “Ref
[13]”, “Ref [11]”, and “Ref [6]” to denote the proposed TS method, the CS-
based TS in [13], the ELM-based TS in [11], and the classic TS method in [6],
respectively. Besides, the “DNN” denotes a four-hidden-layers DNN-based TS
method that has a similar computational complexity as the “Prop”.

###  IV-A Effectiveness Analysis

To analyze the effectiveness of the proposed TS method, Fig. 2(a) depicts the
comparison of error probabilities, where $P=23$,
$\eta=\frac{1}{P}=\frac{1}{23}$ [19], and ${\tau}_{P}$ is 22 sample periods
for testing. For each given signal-to-noise ratio (SNR) in Fig. 2(a), the
“Prop” reaches the smallest error probability of TS among the given TS
methods. Especially, with the increase of SNR, the “Prop” remarkably reduces
the error probability compared with other TS methods. For example, all the
error probabilities of “Ref [13]”, “Ref [11]”, and “Ref [6]” are higher than
$2\times 10^{-2}$ in whole given SNR region, while the error probabilities of
the “Prop” are lower than $10^{-2}$ when SNR$\geq 3$dB. Also, the error
probability of the “Prop” is lower than that of the “DNN” for each given SNR
since its complex parameter tuning results in the difficulty of optimizing the
network parameters. Besides, compared with the “Prop without the relaxed
restriction”, the “Prop” achieves a less performance degradation when testing
${\tau}_{P}$ increases from 22 to 27. This validates the effectiveness of
using the relaxed restriction of propagation delay. Meanwhile, Fig. 2(b) and
Fig. 2(c) depict the error probabilities of TS against the number of sub-
carriers and the length of CP, respectively. Except for those parameters
(presented in Fig. 2), other parameters are the same as those in Fig. 2(a).
For each given SNR in Fig. 2(b) and Fig. 2(c), the “Prop” achieves the lowest
error probability given different values of $N$ and $L_{c}$, respectively. To
sum up, the proposed 1-D CNN-based TS method (i.e., “Prop”) can effectively
reduce the TS’s error probability with the reduced complexity and processing
delay.

###  IV-B Generalization Analysis

To analyze the generalization performance of the proposed method against the
CIR uncertainty, Fig. 2(d) plots the error probability of TS, where the PDPs
of TDL-A, TDL-B, and TDL-C given in 3GPP TR 38.901 [16] are employed for
comparison. It is noteworthy that the relaxed restriction for propagation
delay in Section III-B is adopted for training the “Prop”, while the testing
PDPs of TDL-A, TDL-B, and TDL-C are acquired by setting sample periods
${\tau}_{P}$ as 22, 22, and 23, respectively. According to Fig. 2(d), the
“Prop” achieves the smallest error probability among the given TS methods in
each given channel scenario. This is because the proposed relaxed restriction
increases the completeness of training data, improving the generalization
performance of NN against the variation of CIRs. For example, when SNRs are
greater than $4$dB, the maximum error probability of the “Prop” is smaller
than $8\times 10^{-4}$ for each given channel scenario, while the error
probabilities of the other TS methods are greater than $2\times 10^{-3}$.
Especially for the case where the testing channel scenario is TDL-A, the
“Prop” achieves significant performance improvement in reducing the error
probability. According to empirical simulation results, the PDP of TDL-A
channel is close to the PDPs of training channels, and therefore the “Prop”
performs well under TDL-A channel. As a result, the proposed 1-D CNN-based
timing synchronizer combined with the proposed relaxed restriction for
propagation delay possesses excellent generalization performance against the
CIR uncertainty.

##  V Conclusion

In this letter, a lightweight 1-D CNN-based TS for OFDM is investigated to
alleviate the CIR uncertainty. The developed timing synchronizer highlights
the TS features and thus improves the TS accuracy from the perspective of DL-
based classification tasks. Especially, by carefully designing the filter
size, the number of filters, the network architecture in our timing
synchronizer is simplified, and the computational complexity and processing
delay are reduced compared with those in the CS- and ELM-based timing
synchronizers. With exhaustive experiments, the effectiveness of the proposed
strategy is validated in channel scenarios of 5G (which are given in 3GPP TR
38.901 and have not been used for training), presenting its good
generalization performance against the CIR uncertainty.

## References

  * [1] I. B. F. de Almeida, L. L. Mendes, J. J. P. C. Rodrigues, and M. A. A. da Cruz, “5G waveforms for IoT applications,” _IEEE Commun. Surveys Tuts._ , vol. 21, no. 3, pp. 2554–2567, Apr. 2019.
  * [2] T.-M. Ma, “A novel PRCC scheme for OFDM systems over frequency-selective fading channels,” _IEEE Signal Process. Lett._ , vol. 24, no. 5, pp. 634–637, May 2017.
  * [3] J. Rodríguez-Fernández, “Joint synchronization and compressive channel estimation for frequency-selective hybrid mmWave MIMO systems,” _IEEE Trans. Wireless Commun._ , vol. 21, no. 1, pp. 548–562, Jan. 2022.
  * [4] P. Vitthaladevuni and M. S. Alouini, “Effect of imperfect phase and timing synchronization on the bit-error rate performance of PSK modulations,” _IEEE Trans. Commun._ , vol. 53, no. 7, pp. 1096–1099, Jul. 2005.
  * [5] T. Schmidl and D. Cox, “Robust frequency and timing synchronization for OFDM,” _IEEE Trans. Commun._ , vol. 45, no. 12, pp. 1613–1621, Dec. 1997\.
  * [6] M. Ruan, M. C. Reed, and Z. Shi, “Training symbol based coarse timing synchronization in OFDM systems,” _IEEE Trans. Wireless Commun._ , vol. 8, no. 5, pp. 2558–2569, May 2009.
  * [7] H. Abdzadeh-Ziabari, W.-P. Zhu, and M. N. S. Swamy, “Improved coarse timing estimation in OFDM systems using high-order statistics,” _IEEE Trans. Commun._ , vol. 64, no. 12, pp. 5239–5253, Dec. 2016.
  * [8] A. B. Awoseyila, C. Kasparis, and B. G. Evans, “Improved preamble-aided timing estimation for OFDM systems,” _IEEE Commun. Lett._ , vol. 12, no. 11, pp. 825–827, Nov. 2008.
  * [9] M. M. U. Gul, X. Ma, and S. Lee, “Timing and frequency synchronization for OFDM downlink transmissions using Zadoff-Chu sequences,” _IEEE Trans. Wireless Commun._ , vol. 14, no. 3, pp. 1716–1729, Mar. 2015.
  * [10] J. Liu, K. Mei, X. Zhang, D. McLernon, D. Ma, J. Wei, and S. A. R. Zaidi, “Fine timing and frequency synchronization for MIMO-OFDM: An extreme learning approach,” _IEEE Trans. Cogn. Commun. Netw._ , pp. 1–1, Oct. 2021\.
  * [11] C. Qing, S. Tang, C. Rao, Q. Ye, J. Wang, and C. Huang, “Label design-based ELM network for timing synchronization in OFDM systems with nonlinear distortion,” in _Proc. IEEE 94th Veh. Technol. Conf. (VTC2021-Fall)_ , Sep. 2021, pp. 01–05.
  * [12] C. Qing, W. Yu, B. Cai, J. Wang, and C. Huang, “ELM-based frame synchronization in burst-mode communication systems with nonlinear distortion,” _IEEE Wireless Commun. Lett._ , vol. 9, no. 6, pp. 915–919, June 2020.
  * [13] B. Lopes, S. Catarino, N. M. B. Souto, R. Dinis, and F. Cercas, “Robust joint synchronization and channel estimation approach for frequency-selective environments,” _IEEE Access_ , vol. 6, pp. 53 180–53 190, Sep. 2018.
  * [14] M. Ghogho, D. McLernon, E. Alameda-Hernandez, and A. Swami, “Channel estimation and symbol detection for block transmission using data-dependent superimposed training,” _IEEE Signal Process. Lett._ , vol. 12, no. 3, pp. 226–229, Mar. 2005.
  * [15] T. S. Rappaport _et al._ , _Wireless communications: principles and practice_. prentice hall PTR New Jersey, 1996, vol. 2.
  * [16] 3GPP, “Study on channel model for frequencies from 0.5 to 100 GHz,” Tech. Rep. 3GPP 38.901 (V17.0.0), Mar. 2022.
  * [17] N. Ketkar, _Deep learning with Python: A Hands-on Introduction_ , Apress, Berkeley, CA, 2017.
  * [18] K. Ramasubramanian and K. Baum, “An OFDM timing recovery scheme with inherent delay-spread estimation,” in _Proc. IEEE GLOBECOM_ , vol. 5, Nov. 2001, pp. 3111–3115 vol.5.
  * [19] Z. Xiao, C. Zhang, D. Jin, and N. Ge, “GLRT approach for robust burst packet acquisition in wireless communications,” _IEEE Trans. Wireless Commun._ , vol. 12, no. 3, pp. 1127–1137, Mar. 2013.
  * [20] D. P. Kingma and J. Ba, “Adam: A method for stochastic optimization,” _arXiv:1412.6980_ , 2014.
  * [21] D. Chu, “Polyphase codes with good periodic correlation properties (Corresp.),” _IEEE Trans. Inf. Theory_ , vol. 18, no. 4, pp. 531–532, Jul. 1972.


# OMP-Engineer: Bridging Syntax Analysis and In-Context Learning for Efficient
Automated OpenMP Parallelization

Weidong Wang
Department of Software Engineering
Faculty of Information Technology
Beijing University of Technology
<EMAIL_ADDRESS>
Haoran Zhu
Department of Software Engineering
Faculty of Information Technology
Beijing University of Technology
<EMAIL_ADDRESS>

###### Abstract

In advancing parallel programming, particularly with OpenMP, the shift towards
NLP-based methods marks a significant innovation beyond traditional S2S tools
like Autopar and Cetus. These NLP approaches train on extensive datasets of
examples to efficiently generate optimized parallel code, streamlining the
development process. This method’s strength lies in its ability to swiftly
produce parallelized code that runs efficiently. However, this reliance on NLP
models, without direct code analysis, can introduce inaccuracies, as these
models might not fully grasp the nuanced semantics of the code they
parallelize. We build OMP-Engineer, which balances the efficiency and
scalability of NLP models with the accuracy and reliability of traditional
methods, aiming to enhance the performance of automating parallelization while
navigating its inherent challenges.

_Keywords_ OpenMP $\cdot$ Parallel Computing $\cdot$ Automation

##  1 Introduction

In the contemporary landscape of computing, parallel programming stands as a
pivotal technology, crucial for enhancing computational efficiency and
capitalizing on the capabilities of modern multi-core systems. The ability to
concurrently execute multiple computations not only significantly reduces
processing times but also optimizes the utilization of computational resources
Andrade et al. (2023); Zeng (2023). Despite its advantages, the manual
parallelization of code presents a formidable challenge—marked by its time-
consuming nature and a high propensity for errors. These challenges stem from
the intricate demands of identifying segments of code suitable for parallel
execution, ensuring data consistency, and managing thread synchronization,
among others. The complexity and expertise required to manually parallelize
code have thus fostered the development of automated parallelization
techniques, with two primary methodologies emerging to the forefront: Source-
to-Source (S2S) conversion and Natural Language Processing (NLP)-based
methods.

###  1.1 Source-to-Source Tools

At the heart of S2S approaches lies the principle of transforming sequential
code into its parallel counterpart through automated syntactic modifications.
These tools, grounded in the analysis of code structure and syntax, aim to
streamline the parallelization process by identifying parallelizable code
segments and applying standardized parallelization patterns. The strengths of
S2S methods are manifest in their precision and the reduced likelihood of
introducing errors during the parallelization process, attributed to their
deterministic nature and reliance on established programming paradigms.
However, the resultant parallel code often suffers from drawbacks such as
diminished readability and lower execution efficiency. This is because S2S
transformations tend to prioritize correctness over optimization, leading to
parallelized code that, while functional, may not be optimized for
performance. Additionally, the evolution of parallel programming standards,
exemplified by the continuous updates to OpenMP, poses a significant challenge
for S2S tools. Their inability to rapidly adapt to these evolving standards
means that they can quickly become outdated, limiting their effectiveness and
applicability in modern parallel programming projects.

###  1.2 NLP-based Tools

In contrast, NLP-based parallelization techniques represent a more flexible
approach, leveraging the advancements in machine learning and artificial
intelligence. By analyzing vast datasets of code, these methods train models
capable of understanding both the structure and intent behind code snippets,
thus generating parallel code that is not just syntactically correct but also
optimized for performance. The primary advantage of NLP methods lies in their
adaptability and the high execution efficiency of the generated code. These
approaches are inherently designed to evolve alongside programming standards
like OpenMP, ensuring their long-term relevance and utility. Furthermore, the
broad applicability of NLP techniques across various programming scenarios and
their ability to produce code that aligns with the latest parallelization
paradigms underscore their potential as a transformative force in parallel
programming. However, the reliance on learned patterns without a deep,
semantic understanding of the original code introduces a notable drawback: the
risk of errors. The generated parallel code, while generally efficient, may
occasionally misinterpret the original code’s intent or overlook complex
dependencies, leading to inaccuracies or suboptimal parallelization outcomes.

###  1.3 OMP-Engineer: A Hybrid Approach

Recognizing the limitations inherent in both S2S and NLP methods, we introduce
OMP-Engineer, a novel tool designed to bridge the gap between these
approaches, harnessing their strengths while mitigating their weaknesses. OMP-
Engineer is developed with the aim of providing a robust, adaptable, and
error-resilient solution for the parallelization of code. By integrating the
deterministic, syntax-based analyzation capabilities of S2S methods with the
versatility of NLP techniques, OMP-Engineer offers a comprehensive approach to
automated parallelization.

Our method commences with the generation of the Abstract Syntax Tree (AST) for
the input code, which facilitates a deep syntactic analysis. This step ensures
the parallelization process’s accuracy by accurately identifying code segments
that can be parallelized without error. Following the syntactic analysis, OMP-
Engineer employs in-context learning to instruct Large Language Models (LLMs)
on utilizing OpenMP directives efficiently and correctly. This hybrid approach
enables the system to not only understand the structure of the code but also
to grasp its semantic nuances, allowing for the generation of parallel code
that is both precise and optimized for performance.

##  2 Method

###  2.1 Syntax Analysis

The methodological foundation of OMP-Engineer begins with a detailed syntax
analysis, a critical step in ensuring the accuracy and integrity of the
parallelization process. This analysis is initiated by leveraging ANTLR
(Another Tool for Language Recognition) to construct an Abstract Syntax Tree
(AST) from the source code. The AST serves as a comprehensive representation
of the program’s structure.

Following the generation of the AST, our approach delves into a nuanced
examination of the code’s syntax. The first phase of this examination focuses
on identifying statements that are inherently resistant to parallelization,
such as I/O operations like “printf()”. These operations, due to their
sequential nature, are flagged as non-parallelizable to preserve the semantic
integrity of the program. The second phase of the analysis is dedicated to
scrutinizing the access patterns of variables within the code. By meticulously
tracking how variables are read and written—identifying sequences of access
and potential data dependencies—we can detect the presence of dependencies
that may impede parallel execution.

###  2.2 Educating the LLM through In Context Learning

Upon successfully identifying code segments that are amenable to
parallelization through our syntax analysis phase, we proceed to the second
core component of our methodology: educating the Large Language Model (LLM)
for optimal parallelization.

To achieve this, we introduce a set of In Context Learning (ICL) materials
specifically designed to guide the LLM in understanding and applying OpenMP
directives effectively. These materials consist of a curated collection of
code examples that demonstrate various parallelization patterns, accompanied
by detailed explanations of each pattern’s rationale, applicability, and
implementation nuances. By embedding these examples and explanations directly
into the LLM’s context, we provide it with a rich, focused learning
environment that significantly enhances its ability to generate correct and
efficient parallel code.

##  3 Results

Table 1: Execution time comparison |  | BT | LU | SP
---|---|---|---|---
| Sequential | 122.93 | 102.00 | 83.44
| OMP-Engineer | 52.47 | 56.81 | 44.18
| Autopar | 510.42 | 361.55 | 82.23
| Par4all | 71.01 | 380.06 | 52.19

In our comparative performance evaluation, OMP-Engineer was benchmarked
against two established parallelization tools, Autopar Liao et al. (2009) and
Par4all Amini et al. (2012), using three widely recognized benchmarks: BT, LU,
and SP (all of which are from the NAS benchmark Bailey et al. (1991)). These
benchmarks are instrumental in evaluating the efficiency and effectiveness of
parallel computing solutions. The performance metrics obtained from these
benchmarks are great for demonstrating the superior capability of OMP-Engineer
in optimizing code parallelization.

Our results in Table 1 clearly showcase OMP-Engineer’s outstanding performance
in reducing execution time across all benchmarks when compared to the
sequential (non-parallelized) baseline and the other tools.

The comparison with the sequential execution times illustrates the substantial
performance gains achieved through the application of OMP-Engineer’s
parallelization methodologies. These gains underscore the tool’s effectiveness
in reducing program runtime, thereby enhancing computational efficiency.

It is important to note that despite considering including ChatGPT-generated
parallel code in our evaluation, we encountered excessive inaccuracies in the
parallel code produced by ChatGPT. The high error rate in the parallel code
generated by ChatGPT rendered it infeasible for a fair and meaningful speed
comparison in this context. This decision underscores the challenges inherent
in automated code parallelization and highlights the significance of our
approach with OMP-Engineer, which effectively addresses these challenges
through a combination of syntax analysis and in-context learning for educating
the LLM. Consequently, OMP-Engineer not only ensures the accuracy of
parallelized code but also significantly enhances its execution efficiency, as
evidenced by our benchmark results.

##  4 Conclution and Future Work

In conclusion, our study presents OMP-Engineer, a novel tool designed to
optimize code parallelization through a sophisticated integration of syntax
analysis and in-context learning for Large Language Models. The benchmark
results unequivocally demonstrate OMP-Engineer’s superior performance in
reducing execution times across various tests when compared to existing tools
such as Autopar and Par4all. The innovative approach of educating LLMs with
specific in-context learning materials has proven to be highly effective,
enabling the generation of not only syntactically correct but also
performance-optimized parallel code.

Despite the promising results, there remains ample scope for future work to
further refine and enhance the capabilities of OMP-Engineer. Future directions
could include:

  * •

Expanding the range of parallelization patterns and directives covered by the
in-context learning materials to encompass a wider variety of programming
scenarios and challenges.

  * •

Enhancing the scalability of OMP-Engineer to support larger and more complex
codebases, including those used in high-performance computing (HPC)
environments.

Our work lays a solid foundation for the future of automated code
parallelization, offering promising avenues for both research and practical
applications. As computational demands continue to escalate, OMP-Engineer may
play an increasingly critical role in enabling developers to harness the full
potential of parallel computing technologies efficiently and effectively.

## References

  * Andrade et al. [2023] Gabriella Andrade, Dalvan Griebler, Rodrigo Santos, and Luiz Gustavo Fernandes.  A parallel programming assessment for stream processing applications on multi-core systems.  _Computer Standards & Interfaces_, 84:103691, 2023.
  * Zeng [2023] Guang Zeng.  Performance analysis of parallel programming models for c++.  In _Journal of Physics: Conference Series_ , volume 2646, page 012027\. IOP Publishing, 2023.
  * Liao et al. [2009] Chunhua Liao, Daniel J. Quinlan, Jeremiah J. Willcock, and Thomas Panas.  Extending automatic parallelization to optimize high-level abstractions for multicore.  In Matthias S. Müller, Bronis R. de Supinski, and Barbara M. Chapman, editors, _Evolving OpenMP in an Age of Extreme Parallelism_ , pages 28–41, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg.  ISBN 978-3-642-02303-3.
  * Amini et al. [2012] Mehdi Amini, Béatrice Creusillet, Stéphanie Even, Ronan Keryell, Onig Goubier, Serge Guelton, Janice Onanian Mcmahon, François-Xavier Pasquier, Grégoire Péan, and Pierre Villalon.  Par4All: From Convex Array Regions to Heterogeneous Computing.  In _IMPACT 2012 : Second International Workshop on Polyhedral Compilation Techniques HiPEAC 2012_ , Paris, France, January 2012.  2 pages.
  * Bailey et al. [1991] David H Bailey, Eric Barszcz, John T Barton, David S Browning, Robert L Carter, Leonardo Dagum, Rod A Fatoohi, Paul O Frederickson, Thomas A Lasinski, Rob S Schreiber, et al.  The nas parallel benchmarks—summary and preliminary results.  In _Proceedings of the 1991 ACM/IEEE Conference on Supercomputing_ , pages 158–165, 1991.