-
Wavefront Threading Enables Effective High-Level Synthesis
Authors:
Blake Pelton,
Adam Sapek,
Ken Eguro,
Daniel Lo,
Alessandro Forin,
Matt Humphrey,
Jinwen Xi,
David Cox,
Rajas Karandikar,
Johannes de Fine Licht,
Evgeny Babin,
Adrian Caulfield,
Doug Burger
Abstract:
Digital systems are growing in importance and computing hardware is growing more heterogeneous. Hardware design, however, remains laborious and expensive, in part due to the limitations of conventional hardware description languages (HDLs) like VHDL and Verilog. A longstanding research goal has been programming hardware like software, with high-level languages that can generate efficient hardware…
▽ More
Digital systems are growing in importance and computing hardware is growing more heterogeneous. Hardware design, however, remains laborious and expensive, in part due to the limitations of conventional hardware description languages (HDLs) like VHDL and Verilog. A longstanding research goal has been programming hardware like software, with high-level languages that can generate efficient hardware designs. This paper describes Kanagawa, a language that takes a new approach to combine the programmer productivity benefits of traditional High-Level Synthesis (HLS) approaches with the expressibility and hardware efficiency of Register-Transfer Level (RTL) design. The language's concise syntax, matched with a hardware design-friendly execution model, permits a relatively simple toolchain to map high-level code into efficient hardware implementations.
△ Less
Submitted 10 June, 2024; v1 submitted 29 May, 2024;
originally announced May 2024.
-
Convergence Rates for Stochastic Approximation: Biased Noise with Unbounded Variance, and Applications
Authors:
Rajeeva L. Karandikar,
M. Vidyasagar
Abstract:
In this paper, we study the convergence properties of the Stochastic Gradient Descent (SGD) method for finding a stationary point of a given objective function $J(\cdot)$. The objective function is not required to be convex. Rather, our results apply to a class of ``invex'' functions, which have the property that every stationary point is also a global minimizer. First, it is assumed that…
▽ More
In this paper, we study the convergence properties of the Stochastic Gradient Descent (SGD) method for finding a stationary point of a given objective function $J(\cdot)$. The objective function is not required to be convex. Rather, our results apply to a class of ``invex'' functions, which have the property that every stationary point is also a global minimizer. First, it is assumed that $J(\cdot)$ satisfies a property that is slightly weaker than the Kurdyka-Lojasiewicz (KL) condition, denoted here as (KL'). It is shown that the iterations $J({\boldsymbol θ}_t)$ converge almost surely to the global minimum of $J(\cdot)$. Next, the hypothesis on $J(\cdot)$ is strengthened from (KL') to the Polyak-Lojasiewicz (PL) condition. With this stronger hypothesis, we derive estimates on the rate of convergence of $J({\boldsymbol θ}_t)$ to its limit. Using these results, we show that for functions satisfying the PL property, the convergence rate of SGD is the same as the best-possible rate for convex functions. While some results along these lines have been published in the past, our contributions contain two distinct improvements. First, the assumptions on the stochastic gradient are more general than elsewhere, and second, our convergence is almost sure, and not in expectation. We also study SGD when only function evaluations are permitted. In this setting, we determine the ``optimal'' increments or the size of the perturbations. Using the same set of ideas, we establish the global convergence of the Stochastic Approximation (SA) algorithm under more general assumptions on the measurement error, compared to the existing literature. We also derive bounds on the rate of convergence of the SA algorithm under appropriate assumptions.
△ Less
Submitted 12 May, 2024; v1 submitted 5 December, 2023;
originally announced December 2023.
-
Convergence of Batch Asynchronous Stochastic Approximation With Applications to Reinforcement Learning
Authors:
Rajeeva L. Karandikar,
M. Vidyasagar
Abstract:
Ever since its introduction in the classic paper of Robbins and Monro in 1951, Stochastic Approximation (SA) has become a standard tool for finding a solution of an equation of the form $f(θ) = 0$, when only noisy measurements of $f(\cdot)$ are available. In most situations, \textit{every component} of the putative solution $θ_t$ is updated at each step $t$. In some applications such as $Q$-learni…
▽ More
Ever since its introduction in the classic paper of Robbins and Monro in 1951, Stochastic Approximation (SA) has become a standard tool for finding a solution of an equation of the form $f(θ) = 0$, when only noisy measurements of $f(\cdot)$ are available. In most situations, \textit{every component} of the putative solution $θ_t$ is updated at each step $t$. In some applications such as $Q$-learning, a key technique in Reinforcement Learning (RL), \textit{only one component} of $θ_t$ is updated at each $t$. This is known as \textbf{asynchronous} SA. The topic of study in the present paper is to study \textbf{Block Asynchronous SA (BASA)}, in which, at each step $t$, \textit{some but not necessarily all} components of $θ_t$ are updated. The theory presented here embraces both conventional (synchronous) SA as well as asynchronous SA, and all in-between possibilities. We also prove bounds on the \textit{rate} of convergence of $θ_t$ to the solutions.
As a prelude to the new results, we also briefly survey some results on the convergence of the Stochastic Gradient method, proved in a companion paper by the present authors.
△ Less
Submitted 20 February, 2024; v1 submitted 8 September, 2021;
originally announced September 2021.
-
Umbrella: A Unified Software Defined Development Framework
Authors:
Douglas Comer,
Rajas H. Karandikar,
Adib Rastegarnia
Abstract:
The Northbound (NB) APIs that SDN controllers provide differ in terms of architecture, syntax, naming convention, data resources, and usage. Using NB APIs to write SDN applications makes each application dependent on the API of a specific controller. To bring NB APIs from different vendors under one umbrella and make programming of SDN applications independent of specific controllers, we propose a…
▽ More
The Northbound (NB) APIs that SDN controllers provide differ in terms of architecture, syntax, naming convention, data resources, and usage. Using NB APIs to write SDN applications makes each application dependent on the API of a specific controller. To bring NB APIs from different vendors under one umbrella and make programming of SDN applications independent of specific controllers, we propose a unified software defined development framework that we call Umbrella. This paper presents the key components of the software and reports some preliminary results.
△ Less
Submitted 29 April, 2018;
originally announced May 2018.
