of computing the semantics may cause an exponential increase in the state
space.

These works can be classified by the role of universal quantification: Pichon-
Pharabod and Sewell use universal quantification to define deordering.
Castellan uses it to define interleaving. We define AE-justification using
universal quantification over the possible moves of the opponent.

Unique among these work, we use the standard denotational semantics of
parallel composition for event structures.

Since the initial publication of this paper, Chakraborty and Vafeiadis [2017]
defined an operational semantics for a subset of LLVM, which they extended in
2019. This semantics uses “event structures” to record potentially conflicting
operational steps — these are close in spirit to the pre-configurations of
[Jeffrey and Riely 2014]. As a result, this model is susceptible to the bad
RNG execution discussed above. To avoid it, Chakraborty and Vafeiadis restrict
attention to pre-configurations where are all events are _visible_ : event $e$
is visible if for every write that precedes $e$ in causal+justification order,
there is a write with the same label that does not conflict with $e$.

Cooksey et al. [2018] showed how to simulate several memory models using
fragments of second order logic. They formalized our model and used a
mechanized solver to validate several examples. In particular, they studied
the following program:

y=x; || z=1; || if(!z){x=y;} else {x=1;} ($P_{6}$)
$\mathsf{init}$$\mathsf{W}\smash{{z}\,1}$$\mathsf{R}\,\smash{{z}\,0}$$\mathsf{R}\,\smash{{z}\,1}$$\mathsf{W}\smash{{x}\,1}$$\mathsf{R}\,\smash{{y}\,1}$$\mathsf{R}\,\smash{{y}\,0}$$\mathsf{W}\smash{{x}\,0}$$\mathsf{W}\smash{{x}\,1}$$\mathsf{R}\,\smash{{x}\,1}$$\mathsf{R}\,\smash{{x}\,0}$$\mathsf{W}\smash{{y}\,0}$$\mathsf{W}\smash{{y}\,1}$

Cooksey et al. have established that there is no well-justified configuration
of $P_{6}$ that includes both $(\mathsf{R}\,\smash{{z}\,0})$ and either
$(\mathsf{R}\,\smash{{x}\,1})$ or $(\mathsf{R}\,\smash{{y}\,1})$. The
rationale for forbidding this execution is similar to that for TC5: Pugh
[2004] states that “values are not allowed to come out of thin air, even if
there are other executions in which the thin-air value would have been written
to that variable by some not out-of-thin air means.”

##  9\. Open problems

As far as we are aware, it remains an open problem to define a sensible
semantics that allows the behavior of TC9′ from §7 while disallowing that of
$P_{6}$ from §8. Our model disallows TC9′. Speculative models that rely on
purely existential reasoning allow $P_{6}$; this includes the models of Manson
et al. [2005], Jagadeesan et al. [2010], Kang et al. [2017] and Chakraborty
and Vafeiadis [2019].

_Coherence_ is the property that writes on a single variable appear to occur
in some global order. Our model does enforce coherence on synchronization
variables, where justification implies causal order, but not on plain
variables. For example, in a coherent semantics for (x=1;) || (x=2;) || (r1=x;
r2=x; r3=x;) it is not possible to have
$\texttt{r}_{1}=\texttt{r}_{3}\neq\texttt{r}_{2}$, whereas our semantics
allows this. Our model is not unique in this respect: This outcome is allowed
by the JMM [Manson et al. 2005] and by the _Local DRF_ model of [Dolan et al.
2018]; C++ gives undefined behavior for this program. To enforce coherence on
plain variables, it appears to be necessary to distinguish the causal order
from the order used to determine visibility.

We have modeled synchronization using a restricted form of locks. A coherent
semantics is required to model Java’s volatile variables, and would also allow
a more satisfactory treatment of locks. In the formalization of §6, release
and acquire are both read/write actions. This guarantees that, for example, a
single release does not enable two parallel acquires. In the standard
treatment of locks, assuming coherence, release is a write, and acquire is a
read; thus, release justifies acquire, but acquire does not justify release.
The order between acquire and release is usually guaranteed by thread order,
which we have assumed. This assumption guarantees that the order we have
required from acquire to release is redundant. With a coherent semantics for
locks, the causal order from acquire to release can be dropped.

Separate from the concerns of §7, variations on the definition of well-
justification may be worth exploring. For example, we define of
$\sqsubseteq^{*}$ in terms of $\lesssim^{*}$: when exploring extensions of the
current configuration, both player and opponent are restricted to using
acyclic justification. It is natural to ask about a further definition, which
uses $\sqsubseteq^{*}$ in place of $\lesssim^{*}$. If we let
$\mathord{\sqsubseteq^{*}_{0}}=\mathord{\lesssim^{*}}$ and
$\mathord{\sqsubseteq^{*}_{1}}=\mathord{\sqsubseteq^{*}}$, we can see this as
hierarchy where each $\sqsubseteq^{*}_{i}$ uses $\sqsubseteq^{*}_{i-1}$. It is
not the case that $\sqsubseteq^{*}_{i}$ contains $\sqsubseteq^{*}_{i-1}$,
since the definition uses $\sqsubseteq^{*}_{i-1}$ in both positive and
negative position: positive for the player, and negative for the opponent.
Example 3 is interesting in this regard. If the opponent is allowed to pick
using AE-justification, then the player is unable to well-justify the desired
configuration. Well-justification becomes possible, however, if the opponent
is restricted to acyclically chosen configurations.

We have investigated a very simple program logic, which establishes a
restricted form of safety. It would be interesting to investigate more
powerful logics, such as that of Turon et al. [2014]. One of the primary
purposes of a memory model is to support program transformation. To this end,
it would be useful to have a refinement relation over memory event structures
that preserves well-justification.

Our approach to type safety is novel, in that we have not required a static
association between variables and types as in prior work [Lochbihler 2013;
Goto et al. 2012]. It would be interesting to extend our approach to model
dynamic allocation and deallocation.

## Acknowledgement

Riely was supported by the National Science Foundation under Grant No.
1617175. Any opinions, findings, and conclusions or recommendations expressed
in this material are those of the author and do not necessarily reflect the
views of the National Science Foundation.

The paper have benefited from discussion with JMM working group and the
anonymous referees.

In an earlier version of this paper, Definition 3 of acyclic justification
quantified over $d\in D$ rather than $d\in D\setminus C$. The new definition
was suggested by Simon Cooksey and Mark Batty by email in April, 2019. They
noted that Example 3 failed under the original definition, since the player
configuration $C_{3}$ is not acyclicly justified by $C_{2},$ which is a valid
opponent move.

## References

  * Alglave [2010] J. Alglave.  _A shared memory poetics_.  PhD thesis, Université Paris 7 and INRIA, 2010.
  * Alglave et al. [2014] J. Alglave, L. Maranget, and M. Tautschnig.  Herding cats: Modelling, simulation, testing, and data mining for weak memory.  _ACM Trans. Program. Lang. Syst._ , 36(2):7:1–7:74, 2014.
  * Batty et al. [2011] M. Batty, S. Owens, S. Sarkar, P. Sewell, and T. Weber.  Mathematizing C++ concurrency.  In _Proceedings of the 38th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2011, Austin, TX, USA, January 26-28, 2011_ , pages 55–66, 2011.
  * Batty et al. [2015] M. Batty, K. Memarian, K. Nienhuis, J. Pichon-Pharabod, and P. Sewell.  The problem of programming language concurrency semantics.  In _Programming Languages and Systems - 24th European Symposium on Programming, ESOP 2015, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2015, London, UK, April 11-18, 2015\. Proceedings_ , pages 283–307, 2015.
  * Boehm and Adve [2008] H.-J. Boehm and S. V. Adve.  Foundations of the C++ concurrency memory model.  In _Proceedings of the ACM SIGPLAN 2008 Conference on Programming Language Design and Implementation, Tucson, AZ, USA, June 7-13, 2008_ , pages 68–78, 2008.
  * Castellan [2016] S. Castellan.  Weak memory models using event structures.  In _Vingt-septièmes Journées Francophones des Langages Applicatifs (JFLA 2016)_ , Saint-Malo, France, Jan. 2016.  URL https://hal.inria.fr/hal-01333582.
  * Cenciarelli et al. [2007] P. Cenciarelli, A. Knapp, and E. Sibilio.  The Java memory model: Operationally, denotationally, axiomatically.  In _Programming Languages and Systems, 16th European Symposium on Programming, ESOP 2007, Held as Part of the Joint European Conferences on Theory and Practics of Software, ETAPS 2007, Braga, Portugal, March 24 - April 1, 2007, Proceedings_ , pages 331–346, 2007.
  * Chakraborty and Vafeiadis [2017] S. Chakraborty and V. Vafeiadis.  Formalizing the concurrency semantics of an LLVM fragment.  In _Proceedings of the 2017 International Symposium on Code Generation and Optimization, CGO 2017, Austin, TX, USA, February 4-8, 2017_ , pages 100–110. ACM, 2017.
  * Chakraborty and Vafeiadis [2019] S. Chakraborty and V. Vafeiadis.  Grounding thin-air reads with event structures.  _PACMPL_ , (POPL), 2019.  To Appear.
  * Cooksey et al. [2018] S. Cooksey, S. Harris, M. Batty, R. Grigore, and M. Janota.  PrideMM: A solver for relaxed memory models.  _CoRR_ , abs/1901.00428, 2018.  URL http://arxiv.org/abs/1901.00428.
  * Dolan et al. [2018] S. Dolan, K. C. Sivaramakrishnan, and A. Madhavapeddy.  Bounding data races in space and time.  In _Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2018, Philadelphia, PA, USA, June 18-22, 2018_ , pages 242–255. ACM, 2018.
  * Goto et al. [2012] M. Goto, R. Jagadeesan, C. Pitcher, and J. Riely.  Types for relaxed memory models.  In _Proceedings of TLDI 2012: The Seventh ACM SIGPLAN Workshop on Types in Languages Design and Implementation, Philadelphia, PA, USA, Saturday, January 28, 2012_ , pages 25–38. ACM, 2012.
  * Jagadeesan et al. [2010] R. Jagadeesan, C. Pitcher, and J. Riely.  Generative operational semantics for relaxed memory models.  In _Programming Languages and Systems, 19th European Symposium on Programming, ESOP 2010, Held as Part of the Joint European Conferences on Theory and Practice of Software, ETAPS 2010, Paphos, Cyprus, March 20-28, 2010. Proceedings_ , volume 6012 of _Lecture Notes in Computer Science_ , pages 307–326. Springer, 2010.
  * Jeffrey and Riely [2014] A. Jeffrey and J. Riely.  Event structures and refinement for relaxed memory.  Presentation at the Memory Model Meeting, Cambridge, UK, Sept. 2014.  URL https://perma.cc/BG4K-HSVM.
  * Kang et al. [2017] J. Kang, C.-K. Hur, O. Lahav, V. Vafeiadis, and D. Dreyer.  A promising semantics for relaxed-memory concurrency.  In _Proceedings of the 44th ACM SIGPLAN Symposium on Principles of Programming Languages_ , POPL 2017, pages 175–189, New York, NY, USA, 2017\. ACM.
  * Lamport [1979] L. Lamport.  How to make a multiprocessor computer that correctly executes multiprocess programs.  _IEEE Trans. Comput._ , 28(9):690–691, 1979.
  * Lochbihler [2013] A. Lochbihler.  Making the java memory model safe.  _ACM Trans. Program. Lang. Syst._ , 35(4):12, 2013.
  * Manson et al. [2005] J. Manson, W. Pugh, and S. V. Adve.  The Java memory model.  In _Proceedings of the 32nd ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2005, Long Beach, California, USA, January 12-14, 2005_ , pages 378–391, 2005.
  * Nielsen et al. [1979] M. Nielsen, G. D. Plotkin, and G. Winskel.  Petri nets, event structures and domains.  In _Semantics of Concurrent Computation, Proceedings of the International Symposium, Evian, France, July 2-4, 1979_ , volume 70 of _Lecture Notes in Computer Science_ , pages 266–284. Springer, 1979.
  * Pichon-Pharabod and Sewell [2016] J. Pichon-Pharabod and P. Sewell.  A concurrency semantics for relaxed atomics that permits optimisation and avoids thin-air executions.  In _Proceedings of the 43rd Annual ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages, POPL 2016, St. Petersburg, FL, USA, January 20 - 22, 2016_ , pages 622–633, 2016.
  * Pugh [2004] W. Pugh.  Causality test cases, 2004.  URL https://perma.cc/PJT9-XS8Z.
  * Saraswat et al. [2007] V. A. Saraswat, R. Jagadeesan, M. Michael, and C. von Praun.  A theory of memory models.  In _Proceedings of the 12th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming_ , PPoPP ’07, pages 161–172, 2007.
  * Sezgin [2014] A. Sezgin.  Stress testing.  Private correspondence, Oct. 2014.
  * Turon et al. [2014] A. Turon, V. Vafeiadis, and D. Dreyer.  GPS: Navigating weak memory with ghosts, protocols, and separation.  In _Proceedings of the 2014 ACM International Conference on Object Oriented Programming Systems Languages $\mathbin{\&}$ Applications_, OOPSLA ’14, pages 691–707, 2014.
  * Ševčík [2008] J. Ševčík.  _Program Transformations in Weak Memory Models_.  PhD thesis, Laboratory for Foundations of Computer Science, University of Edinburgh, 2008.
  * Winskel [1986] G. Winskel.  Event structures.  In _Petri Nets: Central Models and Their Properties, Advances in Petri Nets 1986, Part II, Proceedings of an Advanced Course, Bad Honnef, Germany, 8-19 September 1986_ , volume 255 of _Lecture Notes in Computer Science_ , pages 325–392. Springer, 1986.
  * Winskel [1988] G. Winskel.  An introduction to event structures.  In _Linear Time, Branching Time and Partial Order in Logics and Models for Concurrency, School/Workshop, Noordwijkerhout, The Netherlands, May 30 - June 3, 1988, Proceedings_ , volume 354 of _Lecture Notes in Computer Science_ , pages 364–397. Springer, 1988.


Reconfigurable Intelligent Surface-assisted Edge Computing to Minimize Delay in Task Offloading

Mithun Mukherjee1, Vikas Kumar2, Suman Kumar3,
Jaime Lloret4,
Qi Zhang5,
and Mian Guo6

1School of Artificial Intelligence, Nanjing University of Information Science and Technology, China<EMAIL_ADDRESS>
2Bharat Sanchar Nigam Limited, India<EMAIL_ADDRESS>
3Department of Mathematics, IGNTU Amarkantak, MP, India<EMAIL_ADDRESS>
4Universitat Politecnica de Valencia, Spain<EMAIL_ADDRESS>
5DIGIT,  Department of Electrical and Computer Engineering, Aarhus University,   Aarhus, Denmark<EMAIL_ADDRESS>
6School of Electronics and Information, Guangdong Polytechnic Normal University, P.R. China<EMAIL_ADDRESS>
The advantage of computational resources in edge computing near the data source has kindled growing interest in delay-sensitive Internet of Things (IoT) applications. However, the benefit of the edge server is limited by the uploading and downloading links between end-users and  edge servers when these end-users seek computational resources from edge servers. The scenario becomes more severe when the user-end's devices are in the shaded region resulting in low uplink/downlink quality. In this paper, we consider a reconfigurable intelligent surface (RIS)-assisted edge computing system, where the benefits of RIS are exploited to improve the uploading transmission rate. We further aim to minimize the delay of worst-case in the network when the end-users either compute task data in their local CPU or offload task data to the edge server. Next, we optimize the uploading bandwidth allocation for every end-user's task data to minimize the maximum delay in the network. The above optimization problem is formulated as quadratically constrained quadratic programming. Afterward, we solve this problem by semidefinite relaxation. Finally, the simulation results demonstrate that the proposed strategy is scalable under various network settings.

§ INTRODUCTION

In recent years, several industries have been focusing their technological advancement towards high performance computing in cloud data centers. For example, in 2020, NVDIA announced the potential use of DGX A100 NVIDIA’s third-generation Artificial Intelligence (AI) system box [1] that is aimed at the massive gain in performance for AI-related and cutting-edge applications with less power consumption. At the same time, we are witnessing the paradigm changing from constituting a well-run centralized data center infrastructure to the network edge [2, 3, 4, 5], particularly when there is a need to deliver proximity, low-latency, and reliable services for the mission-critical applications, such as remote-surgery, industrial automation and driverless cars. The leading industries with their cloud service providers (e.g., EGX Edge AI platform, NVIDIA RTX graphics with CloudXR, GPU virtualization, and Qualcomm Technologies’ Boundless XR client optimizations [6]
and EdgeConneX [7]) are making their way for the deployment of edge-assisted service provisioning.

§.§ Motivation

Although MEC brings computational, caching, and storage resources towards the network edge, the connectivity and coverage of the access points and base station play critical roles. To say, when end-users aim to avail the computing, caching, and storage resources of edge server, they need to rely on the wireless channels.
Basically, irrespective of application type and service, the uploading/downloading time is an important factor in delay-sensitive service provisioning. This becomes even worse when the network coverage is poor near the cell edge or blocked by obstacles. The uploading and downloading rate and the resulting latency are significantly affected by communication resource allocation. This, in turn, affects the computation delay of end-user's task. To address the above shortcoming that arises due to the connectivity and coverage of the network services, reconfigurable intelligent surface (RIS) [8] can assist MEC.

§.§ Related Work

The role of RIS has been studied in the MEC system, where the end-users aim to offload their computation-intensive tasks to the edge server that resides at the access point [9, 10]. They formulated a latency minimization problem by optimizing the task offloading data size, edge computing resource allocation and RIS phase shift coefficients. To maximize the total amount of data (in terms of bits) processed by end-users and edge server, Chu et al. [11] suggested how to adjust the phase shift of the RIS in addition to the transmit power and time allocation for the end-users, and edge server's computing resource allocation for the end-users. Another study in [12] shows how the edge server adjusts the RIS controller to maximize its revenue while guaranteeing the customized information rate for each end-user. Later, another parallel work studied the RIS-enabled MEC system in [13]. Again, this was to minimize the latency, which is basically calculated as the sum of two end-user's computation offloading time. Moreover, Cao et al. [14] have shown how RIS can resolve the link blockage problem in the mm-Wave MEC system to guarantee real-time offloading from the end-users. This is an interesting and detailed study on how RIS can directly affect the task offloading chances for the end-users that suffer from mm-Wave link blockage.

Recently, over-the-air computation (AirComp) [15] that integrates communication and computation has attracted academia and industries' attention due to its fast data aggregation from IoT devices. However, due to the unreliable channel conditions, the performance of AirComp is severely limited. To address this, RIS [16, 17, 18] has been found a suitable candidate to assist the uplink and downlink transmission.

§.§ Our Contributions and Organization

We summarize our main contributions as follows: We consider an RIS-assisted edge computing system, where end-users offload their task data to the edge server to minimize the overall delay. We aim to leverage the benefits of RIS for the uplink transmission rate in data offloading to the edge server. With the assistance of RIS, a delay-minimization problem is formulated by optimizing the offloading decision variables and bandwidth allocation for the offloaded task data. We formulate the above optimization problem as Quadratically Constrained Quadratic Programming (QCQP) problem. Afterward, we apply semi-definite relaxation (SDR) to solve the problem. Finally, we show that the proposed offloading strategy with RIS can achieve better performance than without RIS assistance and local CPU only approaches.

The rest of the paper is organized as follows. In Section <ref>, we discuss the RIS-assisted MEC system model. We formulate the optimization problem and apply SDR in Section <ref>. The simulation results are presented in Section <ref>. Finally, we conclude our work in Section <ref>.

§ SYSTEM MODEL

(a) An illustration of a RIS-assisted edge computing system with end-users under good and shadowed region. (b) The RIS can assist to improve the uplink and downlink quality for the end-users under shadowed region.

We consider an RIS-assisted edge computing system, as shown in Fig. <ref>. The set of the end-users is denoted as $\mathcal{M} = \{1,2,\ldots, M\}$, where $M$ is the total number of end-users in the network. Due to the limited computational resources (in terms of CPU speed) in local CPU, these end-users often offload task data to edge server when the tasks demand fast processing. Note that among these end-users, we assume that $K$ end-users have good reception quality and the remaining $(M-K)$ end-users are in poor signal reception area.
We denote the end-users in good and poor signal reception areas as the $i$th and the $j$th end-user, respectively, where $i= 1,\,\ldots, \,K$ and $j = (K+1),\, \ldots, \, M$.
We further denote the offloading decision variable for the $m$th end-user at local device of each end-user as $x_{m}$ and  the task processing decision variable at edge server for the end-user as $y_{m}$, where $m = 1,\, \ldots, \, M$ and

\begin{align*}
x_m=& \begin{cases}
\multirow{2}{*}{1}& \text{when the $m$th end-user's task data is }\\
& \text{locally processed,}\\
\multirow{1}{*}{0}& \text{otherwise,}\\
\end{cases}\\
y_m=& \begin{cases}
\multirow{2}{*}{1}& \text{when the $m$th end-user's task data is  }\\
& \text{offloaded and processed at the edge server,}\\
\multirow{1}{*}{0}& \text{otherwise.}\\
\end{cases}
\end{align*}

Note that $x_{m}+y_{m} = 1$. Moreover, these binary decision variables satisfy $x_{m}(1-x_{m}) = 0$  and
$y_{m}(1-y_{m}) = 0$.

§.§ Local Computing Delay

When a task is locally processed by the end-user, the computation  delay becomes

\begin{align}
T^L_i & = \dfrac{x_{i}\, D_i\,L}{f_i^l}\:[\text{s}] \quad i\in \{1,2,\ldots, K\},\\
T^L_{j} & = \dfrac{x_{j}\, D_{j}\,L}{f_{j}^l}\:[\text{s}]\quad {j}\in \{(K+1),\ldots, M\},
\end{align}

where $D_i\text{ and }D_{j}$ is the input data size [bits] of the $i$th and $j$th end-user, respectively, $L$ is the processing density [CPU cycles/bit] for a task, and $f_i$ and $f_j$ denote the CPU clock speed [CPU cycles/s] of the $i$th and $j$th end-user, respectively. We assume equal task processing density for every end-users.

§.§ Offloading Delay for End-users without RIS Assistance

Basically, this is the case when  the end-users are in good signal reception area.  When the $i$th end-user task data is offloaded and processed at the edge server, the offloading delay becomes

\begin{align}
T^\textsf{E}_i = y_i\bigg(\underbrace{\dfrac{D_i}{\eta_i \,\beta_{i}\,C}}_{\text{uploading}}+ \underbrace{\dfrac{D_i\,L}{f_i^e}}_{\text{computation}}\bigg)\:[\text{s}]\:,
\end{align}

where $\eta_i$ is the spectral efficiency of uplink transmission between the $i$th end-user and edge server, $C$ is the total uplink bandwidth, $\beta_i$ is the fraction of total uplink bandwidth allocated to the $i$th end-user, and $f_i^e$ is the CPU rate allocated by the edge server to process the $i$th end-user's offloaded task.

§.§ Offloading Delay for End-users with RIS Assistance

When the $j$th end-user with poor wireless connection offloads its task data to the edge server with RIS assistance, the offloading delay can be written as

\begin{align}
T^\textsf{E}_{j} = y_{j}\bigg(\underbrace{ \dfrac{D_{j}}{\eta_{j}\,\beta_{j}\,C}}_{\text{uploading}}+ \underbrace{\dfrac{D_{j}\,L}{f_{j}^e}}_{\text{computation}}\bigg)\:[\text{s}] \:,
\end{align}

where $\eta_j$ is the spectral efficiency of RIS-assisted uplink transmission between the $j$th end-user and the edge server, $\beta_{j}$ is the fractional value of total uplink bandwidth allocated to the $j$th end-user and $f_j^e$ is the CPU rate  allocated by edge server to process the $j$th end-user's offloaded task.

§ PROBLEM FORMULATION

We write the delay of the worst case in the network as $\max \{(T_{i}^\textsf{L}+ T_{i}^\textsf{E}),\,(T_{j}^\textsf{L}+T_{j}^\textsf{E})\}\forall i\in\mathcal{N}_1,\, j\in\mathcal{N}_2$, where $\mathcal{N}_1=\{1\ldots K\}$, $\mathcal{N}_2=\{K+1,\ldots M\}$.
We aim to minimize the maximum delay by jointly optimizing the task offloading decision vector $\boldsymbol{\xi} = {[x_{m},  y_{m}]}^{\intercal}$ and the bandwidth allocation vector $\mathbf{r} = [\beta_{m}]^{\intercal}$, where

\begin{align}
T^\textsf{L}_i+T^\textsf{E}_i & = \dfrac{D_i\,L\,x_{i}}{f_i^l}
+\dfrac{D_i\,y_{i}}{\eta_i\,\beta_i\,C} +  \dfrac{D_i\,L\,y_{i}}{f_i^e}\:[\text{s}] \:,\\
T^\textsf{L}_{j}+T^\textsf{E}_{j} & = \dfrac{D_{j}L x_{j}}{f_{j}^l}
+\dfrac{D_{j} y_{j}}{\eta_{j}\,\beta_{j}\,C} + \dfrac{D_{j} L y_{j}}{f_{j}^e}\:[\text{s}] \:.
\end{align}

We define the above optimization problem as
\beginmini![2]
ξ,𝐫max{(T_i^+ T_i^), (T_j^+T_j^)}    ∀  i∈𝒩_1,  j∈𝒩_2
∑_i = 1^K β_i +∑_j = K+1^M β_j ≤1,
\endmini!
where the constraint (<ref>) corresponds to the total uplink bandwidth $C$. Now, we take an auxiliary variable $t$ as

\begin{align}
\max\limits_{i\in\mathcal{N}_1,{j}\in\mathcal{N}_2} \big\{(T_{i}^\textsf{L}+ T_{i}^\textsf{E}),\,(T_{j}^\textsf{L}+T_{j}^\textsf{E})\big\} = t\:,\label{1stcvx1}
\end{align}

then, from (<ref>) and (<ref>), we write

\begin{align}
& \dfrac{D_i\,L\,x_{i}\,\beta_i}{f_i^l}
+\dfrac{D_i\,y_{i}}{\eta_i\,C} +  \dfrac{D_i\,L\,y_{i}\,\beta_i}{f_i^e} -\beta_i\,t\le 0,\\
& \dfrac{D_{j}L x_{j}\beta_{j}}{f_{j}^l}
+\dfrac{D_{j} y_{j}}{\eta_{j}\,C} + \dfrac{D_{j} L y_{j}\beta_{j}}{f_{j}^e}-\beta_{j}\,t \le 0.
\label{eqn-aux-var-t2}
\end{align}

Accordingly, the optimization problem becomes
\beginmini![2]
∑_i = 1^K β_i +∑_j = K+1^M β_j ≤1
(7a) and (7b) .
\endmini!

§.§ Vector-matrix Formation

Now, we denote $\mathbf{w}\!=\![x_1,x_2,\ldots, x_K,x_{K+1},\ldots, x_M,y_1,$ $y_2,\ldots, y_K,y_{K+1},\ldots, y_M,\!\beta_1,\!\beta_2,\!\ldots, \beta_K,\beta_{K+1},\ldots, \beta_M,\, t]^{\intercal}$ and define the unit vector as ${\mathbf{e}}_q = [\mathbf{0}_{1 \times (q-1)},\,1,$ $\mathbf{0}_{1 \times (3M+1-q)}]^{\intercal}$. Then, the matrix form of problem (8) can be expressed as

\beginmini![2]
𝐰^⊺𝐀_x,m 𝐰 - 𝐞^⊺_m 𝐰=0

𝐰^⊺𝐀_y,m 𝐰 - 𝐞^⊺_m+M 𝐰=0

𝐞^⊺_m 𝐰+ 𝐞^⊺_m+M 𝐰=1

∑_i = 1^K 𝐞^⊺_i+2M 𝐰  +∑_j = K+1^M 𝐞^⊺_j+2M 𝐰 ≤1

𝐰^⊺𝐀_βx,i 𝐰 +𝐰^⊺𝐀_βy,i 𝐰 + 𝐛_cy,i^⊺𝐰                 +𝐰^⊺𝐀_βt,i 𝐰≤0

𝐰^⊺𝐀_βx,j 𝐰 +𝐰^⊺𝐀_βy,j 𝐰 + 𝐛_cy,j^⊺𝐰                 +𝐰^⊺𝐀_βt,j 𝐰≤0  ,
\endmini!

\begin{align}
& \mathbf{A}_{x,m} = \left[ {\begin{array}{c}
{\mathbf{0}_{(m-1) \times (3M+1)}}\\
\hdashline[2pt/2pt]
\mathbf{e}_{m}^{\intercal} \\
\hdashline[2pt/2pt]
{\mathbf{0}_{(3M+1-m) \times (3M+1)}}
\end{array}} \right], \nonumber \\
& \mathbf{A}_{y,m} = \left[ {\begin{array}{c}
{\mathbf{0}_{(M-1+m) \times (3M+1)}}\\
\hdashline[2pt/2pt]
\mathbf{e}_{(m+M)}^{\intercal} \\
\hdashline[2pt/2pt]
{\mathbf{0}_{(2M+1-m) \times (3M+1)}}
\end{array}} \right], \nonumber \\
& \mathbf{b}_{cy,i} = k_i^c{\mathbf{e}}_{M+i},\,
k_i^l= \dfrac{D_i\,L}{f_i^l},\,
k_i^e= \dfrac{D_i\,L}{f_i^e},\, k_i^c= \dfrac{D_i}{\eta_i C},\nonumber \\
& \mathbf{A}_{\beta x,i}=\dfrac{k_i^l}{2}\left[ {\begin{array}{*{20}{c}} \mathbf{0}_{(i-1) \times (3M+1)}\\
\hdashline[2pt/2pt]
\mathbf{e}_{i+2M}^{\intercal} \\
\hdashline[2pt/2pt]
\mathbf{0}_{(2M-1) \times (3M+1)}\\
\hdashline[2pt/2pt]
\mathbf{e}_{i}^{\intercal} \\
\hdashline[2pt/2pt]
\mathbf{0}_{(M+1-i) \times (3M+1)}
\end{array}} \right],\nonumber \\
& \mathbf{A}_{\beta y,i}=\dfrac{k_i^e}{2}\left[ {\begin{array}{*{20}{c}} \mathbf{0}_{(M-1+i) \times (3M+1)}\\
\hdashline[2pt/2pt]
\mathbf{e}_{i+2M}^{\intercal} \\
\hdashline[2pt/2pt]
\mathbf{0}_{(M-1) \times (3M+1)}\\
\hdashline[2pt/2pt]
\mathbf{e}_{i+M}^{\intercal} \\
\hdashline[2pt/2pt]
\mathbf{0}_{(M+1-i) \times (3M+1)}
\end{array}} \right],\nonumber \\
& \mathbf{b}_{cy,j} = k_{j}^c{\mathbf{e}}_{M+{j}},\,
k_{j}^l= \dfrac{D_{j}\,L}{f_{j}^l},\,
k_{j}^e= \dfrac{D_{j}\,L}{f_{j}^e},\, k_{j}^c= \dfrac{D_{j}}{\eta_{j} C},\nonumber \\
& \mathbf{A}_{\beta t,i}=-\dfrac{1}{2}\left[ {\begin{array}{*{20}{c}} \mathbf{0}_{(2M-1+i) \times (3M+1)}\\
\hdashline[2pt/2pt]
\mathbf{e}_{3M+1}^{\intercal} \\
\hdashline[2pt/2pt]
\mathbf{0}_{(M-i) \times (3M+1)}\\
\hdashline[2pt/2pt]
\mathbf{e}_{i+2M}^{\intercal}
\end{array}} \right],\nonumber\\
& \mathbf{A}_{\beta x,j}=\dfrac{k_{j}^l}{2}\left[ {\begin{array}{*{20}{c}} \mathbf{0}_{({j}-1) \times (3M+1)}\\
\hdashline[2pt/2pt]
\mathbf{e}_{{j}+2M}^{\intercal} \\
\hdashline[2pt/2pt]
\mathbf{0}_{(2M-1) \times (3M+1)}\\
\hdashline[2pt/2pt]
\mathbf{e}_{j}^{\intercal} \\
\hdashline[2pt/2pt]
\mathbf{0}_{(M+1-{j}) \times (3M+1)}
\end{array}} \right],\nonumber \\
& \mathbf{A}_{\beta y,j}=\dfrac{k_{j}^e}{2}\left[ {\begin{array}{*{20}{c}} \mathbf{0}_{(M-1+{j}) \times (3M+1)}\\
\hdashline[2pt/2pt]
\mathbf{e}_{{j}+2M}^{\intercal} \\
\hdashline[2pt/2pt]
\mathbf{0}_{(M-1) \times (3M+1)}\\
\hdashline[2pt/2pt]
\mathbf{e}_{{j}+M}^{\intercal} \\
\hdashline[2pt/2pt]
\mathbf{0}_{(M+1-{j}) \times (3M+1)}
\end{array}} \right],\nonumber
\end{align}

\begin{align}
& \mathbf{A}_{\beta t,{j}}=-\dfrac{1}{2}\left[ {\begin{array}{*{20}{c}} \mathbf{0}_{(2M-1+{j}) \times (3M+1)}\\
\hdashline[2pt/2pt]
\mathbf{e}_{3M+1}^{\intercal} \\
\hdashline[2pt/2pt]
\mathbf{0}_{(M-j) \times (3M+1)}\\
\hdashline[2pt/2pt]
\mathbf{e}_{{j}+2M}^{\intercal}
\end{array}} \right]. \nonumber
\end{align}

§.§ QCQP Formulation

Defining ${\mathbf{z}}=[{\mathbf{w}}^{\intercal}\;1]^{\intercal}$, the problem (9) can be transformed into homogeneous separable QCQP formulation as follows
\beginmini![2]
𝐳𝐳^⊺  𝐁 𝐳
𝐳^⊺  𝐁_x,m 𝐳 =0

𝐳^⊺  𝐁_y,m 𝐳 =0

𝐳^⊺  𝐁_xy,m 𝐳 =1

∑_m = 1^M 𝐳^⊺ 𝐁_β, m 𝐳  ≤1

𝐳^⊺  𝐁_βx y, m 𝐳≤0,
\endmini!

\begin{equation*}
\mathbf{B}= \begin{bmatrix*}[l]
\mathbf{0}_{(3M+1)\times (3M+1)}  &\frac{1}{2}\mathbf{e}_{(3M+1)}\\
\frac{1}{2}\mathbf{e}_{(3M+1)}^\intercal & 0
\end{bmatrix*},
\end{equation*}

\begin{equation*}
\mathbf{B}_{y,m}=\begin{bmatrix*}[l] \mathbf{A}_{y,m} &-\frac{1}{2}{\mathbf{e}}_{M+m}\\
-\frac{1}{2}{\mathbf{e}}_{M+m}^{\intercal} & {0}\\
\end{bmatrix*},
\, \mathbf{b}_{xy,m} = \mathbf{e}_{m}+\mathbf{e}_{m+M}\:,\nonumber
\end{equation*}

\begin{equation*}
\mathbf{B}_{xy,m}=\begin{bmatrix*}[l] \mathbf{0}_{(3M+1)\times (3M+1) } &\frac{1}{2}{\mathbf{b}}_{xy,m}\\
\frac{1}{2}{\mathbf{b}}_{xy,m}^{\intercal} & {0}\\
\end{bmatrix*},
\end{equation*}

\begin{equation*}
\mathbf{B}_{\beta, m}=\begin{bmatrix*}[l]\mathbf{0}_{(3M+1) \times (3M+1) } & \frac{1}{2} {\mathbf{e}}_{m+2M}\\
\frac{1}{2} {\mathbf{e}}_{m+2M}^{\intercal} &0\\
\end{bmatrix*},
\end{equation*}

\begin{equation*}
\mathbf{B}_{\beta x y, m}=\begin{bmatrix*}[l]\mathbf{A}_{\beta x y, m} & \frac{1}{2}{\mathbf{b}}_{cy,m} \\
\frac{1}{2} {\mathbf{b}}_{cy,m}^{\intercal} &0\end{bmatrix*},
\mathbf{B}_{x,m}= \begin{bmatrix*}[l]
\mathbf{A}_{x,m}  &\frac{1}{2}\mathbf{e}_{m}\\
\frac{1}{2}\mathbf{e}_{m}^\intercal & 0
\end{bmatrix*},
\end{equation*}

\begin{align}
& \mathbf{A}_{\beta x y, m}=\mathbf{A}_{\beta x,m} + \mathbf{A}_{\beta y,m}+
\mathbf{A}_{\beta t,m} ,\, \mathbf{b}_{cy,m} = k_{m}^{c}\mathbf{e}_{m+M}\:.\nonumber
\end{align}

Next, we apply the SDR to obtain the desired results. Let $\mathbf{Y} = \mathbf{z}\, \mathbf{z}^\intercal$ with $(\mathbf{Y}) =1$. Then, the separable semi-definite programming (SDP) problem can be expressed by relaxing problem (10) is as follows
\beginmini![2]
𝐘Tr(𝐁 𝐘)
Tr (𝐁_x,m  𝐘) =0

Tr (𝐁_y,m  𝐘) =0

Tr (𝐁_xy,m  𝐘) =1

∑_m = 1^M Tr (𝐁_β, m 𝐘) ≤1

Tr (𝐁_βx y, m 𝐘) ≤0  .
\endmini!
We solve the above SDP problem in a polynomial time using a standard SDP software SeDuMi [19]. We obtain the offloading decision $x_{m}\text{ and }y_{m}$ of the original problem (8) from $\mathbf{Y}$. We use randomization method [20] to find binary offloading decisions. Accordingly, the probability of task processing at end-user and edge server is given as

\begin{align}
P^l_{m} = \dfrac{p^l_{m}}{p^l_{m}(1-p^e_{m})+(1-p^l_{m})\,p^e_{m}}\:,\\
P^e_{m} = \dfrac{p^e_{m}}{p^l_{m}(1-p^e_{m})+(1-p^l_{m})\,p^e_{m}}\:,
\end{align}

where $p^l_{m} = x_{m}$ and $p^e_{m} = y_{m}$. Now, we generate $N$ i.i.d. feasible offloading solutions as $\boldsymbol{\xi}^{(n)} =
[(q^{(n)}_1 )^{\intercal} \ldots (q^{(n)}_M )^{\intercal} ]^{\intercal}$ using the probabilities in (<ref>), for $n =1, \ldots,N$, as follows

\begin{align}
q_{m}\!=\!& \begin{cases}
{[1, \,0]} & \text{with probability}  P^l_{m}\text{ (at local CPU)\:,} \\
{[0,\,1]} & \text{with probability}  P^e_{m}\text{ (at edge server)}\:.
\end{cases}
\end{align}

Next, we solve the problem (5) for the optimal resource allocation corresponding to offloading decision $\boldsymbol{\xi}^{(n)}$ obtained using (13). Therefore, (<ref>) can be rewritten as

\begin{align}
T^\textsf{L}_i+T^\textsf{E}_i & = k_i^f+\dfrac{k_i^{\eta}}{\beta_i}, \\
T^\textsf{L}_{j}+T^\textsf{E}_{j} & = k_j^f+\dfrac{k_j^{\eta}}{\beta_{j}},
\end{align}

where $k_i^f = ({D_i\,L\,x_{i}})/f_i^l+  (D_i\,L\,y_i)/{f_i^e},\, {k_i^{\eta}} = ({D_i\,y_{i}})/({\eta_i\,C}),\, k_j^f = ({D_{j}L\,x_{j}})/f_j^l
+ (D_j\,L\,y_j)/f_j^e,$ and $ k_j^{\eta} = (D_j y_j)/(\eta_j\,C) $. Hence, our optimization problem becomes
\beginmini![2]
𝐫max{(T_i^+ T_i^), (T_j^+T_j^)}    ∀  i∈𝒩_1,  j∈𝒩_2
∑_i = 1^K y_iβ_i +∑_j = K+1^M y_jβ_j ≤1.
\endmini!
Now, we take an auxiliary variable $\theta$ as

\begin{align}
\max\limits_{i\in\mathcal{N}_1,{j}\in\mathcal{N}_2} \big\{(T_{i}^\textsf{L}+ T_{i}^\textsf{E}),\,(T_{j}^\textsf{L}+T_{j}^\textsf{E})\big\} = \theta\:,\label{2ndcvx_1}
\end{align}

and from (<ref>) and (<ref>), we can write

\begin{align}
& k_i^f\,{\beta_{i}}+{k_i^{\eta}}-{\beta_{i}}\,\theta \le 0,\\
& k_j^f\,{\beta_{j}}+{k_j^{\eta}}-{\beta_{j}}\,\theta \le 0\:.
\label{eqn-aux-var-t2}
\end{align}

Then, the optimization problem becomes
\beginmini![2]
(15b), (17a), and (17b) .
\endmini!

§.§ Vector-matrix Formation

We denote ${\mathbf{v}}=[\beta_1,\,\beta_2,\ldots, \beta_K,\,\beta_{K+1},\,\ldots, \beta_M,\, \theta, 1]^{\intercal}$.  Defining a unit vector as ${\mathbf{\hat {u}}}_{p} = [\mathbf{0}_{1 \times ({p}-1)}, 1, \mathbf{0}_{1 \times (M+2-{p})}]^{\intercal}$, the vector-matrix form of problem (18) is written as
\beginmini![2]
∑_i = 1^K 𝐛^⊺_yu,i 𝐯+∑_j = K+1^M 𝐛^⊺_yu,j 𝐯≤1

𝐛_kf,i^⊺ 𝐯 +𝐛_kη,i^⊺𝐯+ 𝐯^⊺ A_βθ, i𝐯≤0

𝐛_kf,j^⊺ 𝐯 +𝐛_kη,j^⊺𝐯+ 𝐯^⊺ A_βθ, j𝐯≤0,
\endmini!

\begin{align}
& \mathbf{b}_{kf,i} = {k_i^f} \mathbf{\hat {u}}_{i},\, \mathbf{b}_{k{\eta},i} = {k_i^{\eta}} \mathbf{\hat {u}}_{M+2},\,
\mathbf{b}_{k,{i}}  = \mathbf{b}_{kf,i} +\mathbf{b}_{k{\eta},i},  \nonumber \\ & \mathbf{b}_{yu,i} = y_i \mathbf{\hat{u}}_i,\,
\mathbf{b}_{kf,j} = {k_j^f} \mathbf{\hat {u}}_{j},\, \mathbf{b}_{k{\eta},j} = {k_j^{\eta}} \mathbf{\hat {u}}_{M+2},\nonumber\\
& \mathbf{b}_{k,{j}}  = \mathbf{b}_{kf,j} +\mathbf{b}_{k{\eta},j}, ~ \mathbf{b}_{yu,j} = y_j \mathbf{\hat{u}}_j\:,\nonumber
\end{align}

\begin{align}
& \mathbf{A}_{\beta \theta, {i}}=-\dfrac{1}{2}\left[ {\begin{array}{*{20}{c}} \mathbf{0}_{(i-1) \times (M+2)}\\
\hdashline[2pt/2pt]
\mathbf{\hat {u}}_{M+1}^{\intercal} \\
\hdashline[2pt/2pt]
\mathbf{0}_{(M-i) \times (M+2)}\\
\hdashline[2pt/2pt]
\mathbf{\hat {u}}_{i}^{\intercal} \\
\hdashline[2pt/2pt]
\mathbf{0}_{(1) \times (M+2)}
\end{array}} \right],\nonumber \\
& \mathbf{A}_{\beta \theta, {j}}=-\dfrac{1}{2}\left[ {\begin{array}{*{20}{c}} \mathbf{0}_{(j-1) \times (M+2)}\\
\hdashline[2pt/2pt]
\mathbf{\hat {u}}_{M+1}^{\intercal} \\
\hdashline[2pt/2pt]
\mathbf{0}_{(M-j) \times (M+2)}\\
\hdashline[2pt/2pt]
\mathbf{\hat {u}}_{j}^{\intercal} \\
\hdashline[2pt/2pt]
\mathbf{0}_{(1) \times (M+2)}
\end{array}} \right]\:.\nonumber
\end{align}

Let  ${\mathbf{s}}^{\intercal}=[{\mathbf{v}}^{\intercal}\;1]^{\intercal}$, thus the objective function becomes
\beginmini![2]
𝐬𝐬^⊺  𝐇 𝐬

∑_i=1^K 𝐬^⊺  𝐇_β, i 𝐬 + ∑_j=K+1^M 𝐬^⊺  𝐇_β, j 𝐬  ≤1

𝐬^⊺  𝐇_βk θ, i 𝐬 ≤0

𝐬^⊺  𝐇_βk θ, j 𝐬 ≤0,
\endmini!

\begin{equation*}
\mathbf{H}= \begin{bmatrix*}[l]
\mathbf{0}_{(M+2)\times (M+2)}  &\frac{1}{2}\mathbf{\hat {u}}_{(M+1)}\\
\frac{1}{2}\mathbf{\hat {u}}_{(M+1)}^\intercal & 0
\end{bmatrix*}, \nonumber
\end{equation*}

\begin{equation*}
\mathbf{H}_{\beta, i}= \begin{bmatrix*}[l]
\mathbf{0}_{(M+2)\times (M+2)}  &\frac{1}{2} \mathbf{b}_{yu,i}\\
\frac{1}{2} \mathbf{b}_{yu,i}^\intercal & 0
\end{bmatrix*}, \nonumber
\end{equation*}

\begin{equation*}
\mathbf{H}_{\beta, j}= \begin{bmatrix*}[l]
\mathbf{0}_{(M+2)\times (M+2)}  &\frac{1}{2} \mathbf{b}_{yu,j}\\
\frac{1}{2} \mathbf{b}_{yu,j}^\intercal & 0
\end{bmatrix*}, \nonumber
\end{equation*}

\begin{equation*}
\mathbf{H}_{\beta k\theta, i}= \begin{bmatrix*}[l]
\mathbf{A}_{\beta \theta, i}  & \dfrac{1}{2}\mathbf{b}_{k,i}\\
\dfrac{1}{2}\mathbf{b}_{k,i}^\intercal & 0
\end{bmatrix*},
\,\mathbf{H}_{\beta k\theta, j}= \begin{bmatrix*}[l]
\mathbf{A}_{\beta \theta, j}  & \dfrac{1}{2}\mathbf{b}_{k,j}\\
\dfrac{1}{2}\mathbf{b}_{k,j}^\intercal & 0
\end{bmatrix*}\:.
\end{equation*}

Further, applying the SDR to obtain the desired results, let $\mathbf{S} = {\mathbf{s}}\, {\mathbf{s}}^\intercal$ such that $(\mathbf{S}) =1$. Then, the SDP problem, by relaxing problem (20), can be expressed as
\beginmini![2]
𝐒Tr(𝐇 𝐒)

∑_i=1^K Tr (𝐇_β, i 𝐒) + ∑_j=K+1^M Tr (𝐇_β, j 𝐒) ≤1

Tr (𝐇_βk θ, i 𝐒) ≤0

Tr (𝐇_βk θ, j 𝐒) ≤0 .
\endmini!
We solve the above SDP problem (21) in a polynomial time, denoting $\mathbf{S}$ as the optimal solution of the SDP problem (21). Finally, we obtain the optimal values of $\beta_i$ and $\beta_j$ from $\mathbf{S}$.

§ SIMULATION RESULTS

Delay performance vs. total uplink bandwidth.

Delay performance with computing resource in edge server.

In this section, we evaluate the performance of the proposed RIS-assisted computation offloading policy with Monte Carlo simulations. Unless specified, we set CPU clock speed of end-user, i.e, $f_i^l=f_j^l=500\!\times\!10^6$ [cycles/second] and edge server, i.e., $f^\textsf{E}=5\!\times\!10^9$ [cycles/second].
We assume that edge server equally distributes its CPU clock speed, $f^\textsf{E}$, to every end-users, i.e., $f_i^e = f_j^e= f^\textsf{E}/M$. We further consider that the size of a single task is uniformly distributed over $[0.1,0.9]$ [MB] with a task processing density, $L=1900$ [cycles/byte]. Also, the total available uplink bandwidth is $C=15$ [MHz]. We assume that $M=8$ end-users, out of which $(M-K)=3$ end-users have poor wireless connection. Moreover, we set $\eta_i = 3.5$ [bps/Hz], $\eta_{j} = 0.1$ [bps/Hz] without RIS and $\eta_{j}=3$ [bps/Hz] with RIS. We further set $N=10$ as in [20].  The simulation results[The source code is available at <https://github.com/MithunHub/GC2021Offloading>. ] are averaged over at least 10,000 different runs.

Fig. 2 illustrates the maximum delay performance over the network with different uplink bandwidth. When we consider `standalone edge server', the entire data is offloaded to the edge server. Thus, at lower uplink bandwidth, the worst performance is observed due to high uploading delay. From the figure, we can see that the maximum delay decreases with the increase of uplink bandwidth. The main reason is the uplink transmission delay decreases with the increase of uplink bandwidth. Therefore, the maximum delay over the network decreases. It is interesting to see that with RIS assistance, the maximum value of delay further reduces. Note that in this paper, we aim to minimize the maximum delay experienced by any end-user in the networks. Therefore, when no RIS support is available to the end-users with poor connection, the delay of these end-users has the adverse effect in minimizing the maximum value of delay in the network. Hence, reducing the uplink transmission delay with RIS assistance results in decreasing the maximum delay over the network.

Moreover, to show the performance with the computation resources in the edge server, Fig. 3 presents the maximum delay with increasing the CPU cycles/second of the edge server. From the figure, we observe that increase in CPU rate $f^\textsf{E}$ at the edge reduces the maximum delay. Moreover, one can clearly see that the offloading approach with RIS assistance exhibits better performance than the case without RIS assistance. In addition, we observe that at very high CPU cycles/second, the performance of standalone edge server and optimal offloading with RIS assistance gets very close to each others. Because, edge server's CPU rate is so high that end-users always prefer to offload the tasks under the setting of uplink data rate.

§ CONCLUSIONS

In this paper, we studied computation offloading in a reconfigurable intelligent surface-assisted edge computing system. We employed the benefits of RIS to improve the uploading transmission rate for end-users with poor connection. Our proposed offloading scheme optimized the binary offloading decision variable, the uploading bandwidth allocation, and the CPU frequency allocated for the task data by the edge server. We applied SDR to solve the above QCQP problem. We note that with a better uplink quality, the poor user enjoys more chances to use the computational resources of the edge server, thereby improving the overall network performance than without RIS assistance. Our future work includes studying reliability and deadline constraints in task data offloading for an RIS-assisted edge computing system.

§ ACKNOWLEDGMENT

This work was supported in part by the National Natural Science Foundation of China under Grant 61901128 and Nanjing University of Information Science and Technology Start-up Fund Grant 1521632101005. The corresponding author is Mian Guo.

[1]
T. Paikeday, “AI as you like it: NVIDIA DGX-ready partners make AI
adoption easy,” 2020, accessed on: July 20 2020. [Online]. Available:
[2]
C.-F. Liu, M. Bennis, M. Debbah, and H. V. Poor, “Dynamic task offloading and
resource allocation for ultra-reliable low-latency edge computing,”
IEEE Trans. Commun., vol. 67, no. 6, pp. 4132–4150, June 2019.

[3]
J. Liu and Q. Zhang, “To improve service reliability for AI-powered
time-critical services using imperfect transmission in MEC: An experimental
study,” IEEE Internet of Things J., vol. 7, no. 10, pp. 9357–9371,
Oct. 2020.

[4]
M. Mukherjee, M. Guo, J. Lloret, and Q. Zhang, “Leveraging intelligent
computation offloading with fog/edge computing for Tactile internet:
Advantages and limitations,” IEEE Netw., vol. 34, no. 5, pp.
322–329, 2020.

[5]
D. E. Boubiche, A.-S. K. Pathan, J. Lloret, H. Zhou, S. Hong, S. O. Amin, and
M. A. Feki, “Advanced industrial wireless sensor networks and intelligent
IoT,” IEEE Commun. Mag., vol. 56, no. 2, pp. 14–15, Feb. 2018.

[6]
“Making boundless XR a commercial reality: Kicking off a trial to utilize
existing 5G release-15 features to make XR available at scale,” 2020,
accessed on: July 20 2020. [Online]. Available:
[7]
“Edgeconnecx,” <https://www.edgeconnex.com>, accessed on: July 20 2020.

[8]
E. Basar, M. Di Renzo, J. De Rosny, M. Debbah, M. S. Alouini, and
R. Zhang, “Wireless communications through reconfigurable intelligent
surfaces,” IEEE Access, vol. 7, pp. 116 753–116 773, 2019.

[9]
T. Bai, C. Pan, Y. Deng, M. Elkashlan, A. Nallanathan, and
L. Hanzo, “Latency minimization for intelligent reflecting surface aided
mobile edge computing,” IEEE Journal on Selected Areas in
Communications, vol. 38, no. 11, pp. 2666–2682, Nov. 2020.

[10]
T. Bai, C. Pan, H. Ren, Y. Deng, M. Elkashlan, and A. Nallanathan,
“Resource allocation for intelligent reflecting surface aided wireless
powered mobile edge computing in OFDM systems,” IEEE Transactions on
Wireless Communications, 2021, to be published.

[11]
Z. Chu, P. Xiao, M. Shojafar, D. Mi, J. Mao, and W. Hao,
“Intelligent reflecting surface assisted mobile edge computing for internet
of things,” IEEE Wireless Commun. Lett., vol. 10, no. 3, pp.
619–623, Mar. 2021.

[12]
Y. Liu, J. Zhao, Z. Xiong, D. Niyato, C. Yuen, C. Pan, and B. Huang,
“Intelligent reflecting surface meets mobile edge computing: Enhancing
wireless communications for computation offloading,”
arXiv:2001.07449, 2020.

[13]
F. Zhou, C. You, and R. Zhang, “Delay-optimal scheduling for IRS-aided
mobile edge computing,” IEEE Wireless Commun. Lett., vol. 10, no. 4,
pp. 740–744, Apr. 2021.

[14]
Y. Cao, T. Lv, Z. Lin, and W. Ni, “Delay-constrained joint power
control, user detection and passive beamforming in intelligent reflecting
surface-assisted uplink mmwave system,” IEEE Transactions on Cognitive
Communications and Networking, 2021.

[15]
W. Liu, X. Zang, Y. Li, and B. Vucetic, “Over-the-air computation systems:
Optimization, analysis and scaling laws,” IEEE Trans. Wireless
Commun., vol. 19, no. 8, pp. 5488–5502, Aug. 2020.

[16]
W. Fang, M. Fu, K. Wang, Y. Shi, and Y. Zhou, “Stochastic
beamforming for reconfigurable intelligent surface aided over-the-air
computation,” in Proc. IEEE GLOBECOM, Dec. 2020, pp. 1–6.

[17]
Z. Wang, Y. Shi, Y. Zhou, H. Zhou, and N. Zhang, “Wireless-powered
over-the-air computation in intelligent reflecting surface-aided IoT
networks,” IEEE Internet of Things J., vol. 8, no. 3, pp. 1585–1598,
Feb. 2021.

[18]
M. Mukherjee, V. Kumar, M. Guo, D. B. da Costa, Z. D. Ertugrul Basar, and W. K.
Wong, “The interplay of reconfigurable intelligent surfaces and mobile edge
computing in future wireless networks: A win-win strategy to 6G,”
arXiv:2106.11784, 2021. [Online]. Available:
[19]
M. Grant and S. Boyd, “CVX: Matlab software for disciplined convex
programming, version 2.1,” <http://cvxr.com/cvx>, Mar. 2014.

[20]
M.-H. Chen, M. Dong, and B. Liang, “Resource sharing of a computing access
point for multi-user mobile cloud offloading with delay constraints,”
IEEE Trans. on Mobile Comput., pp. 1–13, 2018.