An optimal architecture for a multi-standard reconfigurable radio: A network theory re-formulation

Please download to get full document.

View again

of 5
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Information Report
Category:

Word Search

Published:

Views: 0 | Pages: 5

Extension: PDF | Download: 0

Share
Related documents
Description
An optimal architecture for a multi-standard reconfigurable radio: A network theory re-formulation
Tags
Transcript
  An optimal architecture for a multi-standard reconfigurable radio:Cost-minimising common operators under latency constraints Virgilio RODRIGUEZ, Christophe MOY, Jacques PALICOTSCEE LaboratoryIETR/SupelecCesson-Sevigne, Francee-mail: vr <at> ieee.org, {christophe.moy, jacques.palicot}@supelec.fr  Abstract —We build a mathematical model to de-termine an optimal architecture for a multi-standardreconfigurable radio. We examine the trade-off between(a) building complex dedicated functional modules pro-viding high performance at a high cost (as well assize and weight) (“Velcro approach”), versus (b) relyingon simpler lower-level components, which reduces costbut increases system latency. On the foundation of the“common operators” approach, we describe a procedurethat identifies an architecture that minimises the cost of the radio, while keeping its latency under specified limits. I. I NTRODUCTION We build a mathematical model to identify the op-timal architecture for a multi-standards reconfigurableradio. The basic trade-off we examine is that of the(monetary) cost of a multi-standard reconfigurableradio versus its performance. We find an architecturewhich minimises the cost, while observing perfor-mance (computational time) constraints.We model the radio as a hypergraph of progressivelysimpler functional modules. The functionality of onesuch module can be provided either through a self-contained component, or through the invocation of simpler (lower level) modules. A self-contained com-ponent is an optimised hardware/software combinationbuilt to perform a task in the most efficient way. Onesuch component could be an equaliser, for example.Simpler, lower-level components are generally lessexpensive to build, and can be reused by several upper-level modules inside and across standards. The useof lower-level components reduces the manufacturingcost, and quite possibly the size and the weight of the radio. Unfortunately, such use generally increasesthe execution time of the concerned task. As a conse-quence, the total execution time of a given operationmay exceed practical limitations.Thus, we see the design of a multi-standard recon-figurable radio as choosing the optimal point betweentwo extremes. At one extreme is the Velcro approach:to install self-contained complex communication mod-ules each exclusively dedicated to a given standard. Atthe other extreme, we can attempt to build the entiremulti-standard radio through very simple components(adders, multipliers, MAC, etc) that are invoked bymore complex modules to perform the various commu-nication tasks necessitated by the supported communi-cation standards. The Velcro approach will generallyprovide the best performance, but at the highest cost(and probably greatest size and weight). Conversely,by going to the other extreme, we can minimise the(monetary) cost (and the size and weight) of the radio,but at a performance level that may be unacceptable.Thus, we need to find the right level of complexity forthe various modules that gives us the best trade-off between performance and cost.This study is based on the “common operators”approach to the design of reconfigurable equipment.Its main principle is the identification and (re)useof common operators that can each match severalprocessing contexts by a simple parameter adjustment.To achieve, from this perspective, an optimal archi-tecture capable of supporting several communicationstandards, one must identify an optimal level of com-plexity for various functional modules. The selectedmodules may be simpler than a self-contained modulethat implements a major communication task (such asequalisation or modulation), but more complex thanprimitive operators such as AND, OR, adder, etc.This approach can greatly increase the efficiency of amulti-standard software-defined radio, both in terms of manufacturing cost, and of the speed of reconfigurationduring operation.The common operators approach is discussed moreextensively in [1], a work   not   focused on architectureoptimisation. In [2], a parallel strand of work, we fol-lowed an approach similar to the present one. However,[2] combines economic and latency considerations intoa single cost function. This combination (a weightedsum) is a reasonable first step, as it simplifies the ex-position and the solution algorithm. But unfortunately,the combined cost function has some drawbacks: itadds the monetary cost (paid once by the designer)with the “delay costs” incurred by the user eachtime it executes a standard throughout the useful lifeof the radio, it fails to account for the hard timeconstraints often arising from communication applica-tions, and makes the chosen design highly dependenton the weights (which are themselves arbitrary). In thepresent paper, we minimise the (monetary) cost only.  Latency plays a role, as a constraint that cannot beexceeded while performing certain operations. Neither[2] nor the present work addresses the identificationof new common operators useful to the design of multi-standard reconfigurable radios. Such identifica-tion is, in its own right, an active area of research.Researchers are proceeding along several directions.For instance, [3] shows that many important tasks of acommunication receiver can be implemented throughthe fast Fourier transform (FFT). In turn, the FFTcan be implemented via the butterfly operator, and,as argued more recently[4], via CORDIC. With this inmind, some researchers are seeking frequency-domainimplementations for different families of algorithms.For example, [5] studies the frequency domain imple-mentation of Reed-Solomon channel decoding.Relevant works describing interesting approaches tothe design of reconfigurable radios include: [6], [7],which argue for parametrised design from a “commonfunctionality” perspective, as srcinally advocated in[8]; [9] whose approach is inspired by object-orientedprogramming; [10] which attempts to cover hardwareand software design under a common methodology;and [11] which proposes designs that integrate theentire system on a chip (SoC).The rest of the paper proceeds as follows. First, webuild the mathematical model. This step includes thedrawing of a graph that represents design alternatives,the consideration of possible performance metrics, andthe specification of a cost function and appropriateconstraints. Subsequently, we discuss the optimisationprocedure, whose results we give and discuss in animmediately following section. Finally, we concludewith a discussion addressing further interpretations of our results, as well as limitations and future directions.II. M ATHEMATICAL MODEL  A. Graph-theoretic representation As illustrated by figure 1, we represent a multi-standard radio as a hypergraph of progressively simplerfunctional modules. Each node (module) representsa functionality that can either be implemented viaa dedicated hardware/software component (an ASICfor example), or can be achieved by invoking lower-level modules. The hyperarcs leaving a node (parent)specify the simpler modules (descendants) that couldprovide the required functionality through multiplecalls. Descendant nodes may not all be at the samelevel.An OR arc (direct arrow) means that only one of the descendant nodes is necessary to implement thefunctionality of the parent node. An AND arc (invertedY connection as pointing from  S  3 to  A 4 and  A 5) meansthat  all  descendant nodes are needed to implement thefunctionality of the parent node. Note that in somecases, a parent node may have both AND and ORdependencies with its descendants. The roots of thisgraph, at the highest level, represent the standards to Fig. 1. Graph corresponding to a conceivable tri-standard recon-figurable radio be supported by the radio. Below, we do  not   considerthe possibility that the graph may be cyclic, whichwould complicate the exposition and analysis.  B. Optimisation parameters The decision to provide a functionality via a self-contained, dedicated component or by invoking multi-ple times simpler, reusable components is determinedby two key considerations: (monetary) cost and (exe-cution) time.The monetary cost of a component which is paidonly once during the useful life of the radio) representsthe total cost of including the component in the design.In some software-defined radio (SDR) architectures,the monetary cost can be represented by (is propor-tional to) the number of logic units necessitated byan FPGA implementation. It is best to take the viewpoint of a system integrator that “outsources” the com-ponents (software or hardware). Then, the monetarycost represents the fair-market value, at design time, of acquiring the finished component in the open market.Execution time (incurred every time a component isemployed throughout the life of the system) is alsoa critical consideration, because communication stan-dards may impose hard time constraints (deadlines) forthe completion of certain operations.Determining the “deadlines” to be observed whiledesigning the radio to support a given standard is non-trivial and should be done with great care. If deadlinesare set too high, they may lead to a design that fails toperform at acceptable levels in practical situations. Butif deadlines are set lower than necessary, the resultingdesign will be more expensive than necessary. Thekey to determining the right delay tolerances is toexamine the “transmission chain” (the block diagramdepicting the various steps necessary to establish end-to-end communication under a considered standard, asshown by figure 2), and the numerical specificationsgiven by the standard bodies. A chosen architecturemust yield a performance able to support end-to-endcommunication under the considered standards. We do  Fig. 2. The key to determining appropriate “deadlines” is anexamination of the “transmission chain”. This corresponds to GSM,but our development does not specifically target that standard. not further address here the determination of thesedeadlines, and assume that the pertinent informationhas been obtained elsewhere and given to us. C. Optimisation problem Let: S  i  with  i = 1 ,...,  I   be the standards to be supported, δ i  the “design deadline” of standard  S  i F  k   with  k   =  1 ,..., K   be 0-1 variables such that  F  k   = 1 if component  k   is chosen to be installed in self-contained (dedicated) form. C  k   and  T  k   be respectively the (monetary) cost andthe execution time of module  k   (if self-contained) τ i ( F  1 , F  2 ,..., F  K  )  be the time of executing the tasksused to calculate the “deadline” of standard  i  for aparticular choice of componentsNotice that not all the possible choices are ac-ceptable. For example, if there are three root nodes(standards), and the self-contained components thatcan each execute an entire standard (for the “Vel-cro” design) are labelled 1,2, and 3, then, the point ( 1 , 1 , 1 , 0 , 0 ,..., 0 , 0 ) , which means setting  F  1  =  F  2  = F  3  =  1 and all others  F   j  =  0, is in principle acceptable(but not necessarily optimal!... this is the “Velcro” ar-chitecture). But some other choices would  not   supportthe desired standards (for example  ( 0 , 0 ,..., 0 ) , whichmeans building nothing at all, is clearly unacceptable.Let  Ω  denote the set of all K-tuples of binarynumbers that correspond to acceptable choices of theset of components (this is information taken directlyfrom the hypergraph).Then we seek to solve: Fig. 3. Partial hypergraph with some design parameters, and aplausible solution min ( F  1 , F  2 ,..., F  K  ) ∈ Ω ∑ F  k  C  k  subject to τ 1 ( F  1 , F  2 ,..., F  K  ) ≤ δ 1  (1)... τ  I  ( F  1 , F  2 ,..., F  K  ) ≤ δ  I  III. S OLVING THE OPTIMISATION In principle the preceding problem can be solvedsimply by computing the cost of every feasible choiceof components (that supports the desired standards andobeys the deadlines), and choosing the one of minimalcost. For larger problems, a “smarter” algorithm isneeded. Below we provide an illustration which canbe solved with minimal computing effort.  A. A realistic illustration Figure 3 (representing an evolution of a figure from[2]) shows a sub-graph corresponding to the decom-position of several processing elements (equalisation,multi-channel, OFDM) that could be part of a multi-standard radio system. The sub-graph is  not   intendedto show  all  the possible alternative implementationsfor each of the considered processing elements. Rootnodes (standards) are  not   shown.The equalisation block compensates for the multi-path impairment typical of wireless channels. It can beeither implemented through a finite-impulse responsefilter (FIR) or through the fast Fourier transform (FFT)operator. The implementation of equalisation in thefrequency domain is particularly attractive for channels  that exhibit long impulse responses, which leads to FIRfilters with a very high number of taps. Notice that theinverse FFT is computationally equivalent to the FFT;thus, we attach a multiplicative factor of 2 to the arcpointing from the equaliser to the FFT.Multi-channel refers to the channelisation functionof a cellular base station. This can be accomplishedvia the “classical” channel per channel procedure, orby proceeding in parallel, through a filter-bank chan-neliser (which can be implemented via FFT). Otherlower-level modules correspond to well-known signalprocessing constructs.The graph shows that at least the FFT operator isneeded to implement OFDM. The graph also showsthat both equalisation and OFDM could employ thesame FFT operator, although it is optional for FIR-based equalisation. A reconfigurable FFT componentcould provide the functionality of FFT operators of different orders.The numerical values near the bottom right of ablock represent cost / time associated with the com-ponent that could provide that functionality. The unitsof measurements are immaterial for our purposes. Weonly need relative figures, to be able to compare onedesign alternative to another. But the time figures mustbe consistent with those in which the deadlines areexpressed. At the top left there is a numerical identifierfor the corresponding module.The arcs are tagged with a number of calls (NoC)figure. When a node is needed several times by ahigher level module, it is called several times, and notphysically replicated. Accordingly, the multiple callsaffect the latency of the system, but not its monetarycost.  B. Results and interpretations The sub-graph of figure 3 is small enough to besolved by exhaustive search, although the number of design alternatives quickly explodes. The thick dottedlines in figure 3 show an FFT-only design, which is aconceivable outcome of the optimisation, for a specificset of deadlines.Figure 4 provides a summary of our solution proce-dure, and shows some interesting design alternatives.For this illustration, we have ignored the designs thatuse the simplest (lowest level) components (adder,multiplier, etc). Thus, the simplest considered com-ponent is the CORDIC. A one in the column corre-sponding to a module means that, in that particulardesign, the module is implemented via a dedicatedcomponent.  T  1,  T  2 and  T  3 are the execution timescorresponding to OFDM, equalisation and the chan-neliser for a given design. The deadlines should beapplied to the entire transmission chain (not to individ-ual tasks). Nevertheless, for the sub-design illustrationunder consideration, we pretend that the tasks at thetop of the graph have associated deadlines (determinedby the supported communication standards). We haveconsidered that an order-64 FFT operator satisfies ourrequirements, and that the multi-channeliser handles25 channels.The “Cost” column shows that the least expensivedesign consists of a CORDIC component only, butit performs slowly. This would be the chosen designif the deadlines are, for example, 6 200, 12 300and 320 000 respectively (recall that time units havenot been specified here). If the deadlines are tighter,the CORDIC-only design falls outside the feasibilityregion. Then other candidates may be chosen. Forexample, the butterfly-only design performs a gooddeal better in all three tasks, and is only marginallymore expensive. The FFT-only design costs about70 times more than the butterfly-only alternative, butperforms 7-8 times better, and could very well bethe optimal choice under tighter time constraints. The“Velcro” solution performs best and costs most, as itimplements the top modules with dedicated compo-nents. The FFT-only design is far behind the Velcroapproach only with respect to  T  3 (multi-channeliser).The performance gap between the FFT-only design andVelcro narrows considerably if one adds a filter bank.This combination provides performance near Velcro’s,for about one quarter of the cost.IV. D ISCUSSION AND OUTLOOK We have built a mathematical model that enablesus to identify an architecture for a multi-standardreconfigurable radio, which minimises the cost of theradio while observing pertinent execution time con-straints. The chosen architecture represents an optimalpoint between two extremes: (i) highly complex com-munication components each exclusively dedicated toa given standard (“Velcro” approach), and (ii) verysimple components to be invoked by “higher layers”in support of the various standards. We representedthe radio as a hypergraph of progressively simplerfunctional modules.We have illustrated our approach through a simpli-fied “sub-design”, which is suffciently close to realityto provide useful insights. Our results agree with intu-ition. When the execution time constraints imposed bythe supported standards on the considered high-levelmodules are very tight, the more complex dedicatedcomponents need to be chosen. On the other hand,if the time constraints are lenient, money is saved bysupporting the standards through simpler (lower-level)components, such as the FFT, butterfly or even theCORDIC operator. Our analysis also sheds some lighton some of the economic issues that may arise whena single architecture targets several communicationstandards. An optimal architecture that exclusivelysupports standards oriented to “slow” applications,such as voice, and text messaging, will favour lower-cost simpler, reusable components. Thus, a consumerprimarily interested in such “traditional” applicationswill be better off by purchasing equipment that sup-  Fig. 4. Some interesting design alternatives. A one in the column corresponding to a module means that it is implemented via a dedicatedcomponent.  T  1,  T  2 and  T  3 are the execution times corresponding to OFDM, equalisation and the multi-channel channeliser for a givendesign. The “Cost” column shows that the least expensive design consists of a CORDIC component, exclusively, but it performs slowly.The “Velcro” solution (bottom) performs fastest but costs most, as it implements the top modules with dedicated components. ports only a few simple communication standards. Inother words, certain care must be taken in choosingthe set of standards to be supported by reconfigurableradios.Many important issues remain to be addressed. Forexample, building the hypergraph of design choices isitself an object of research, as it is the adaptation of the graph to the evolution of communication standards.Likewise, finding an efficient algorithm to explorethe solution space is a short-term objective of ours.Other important issues include consideration of (i) thetime needed to re-configure the radio while switchingfrom a standard to another, (ii) the “travel time” of signals from a component to another, and (iii) thepossible contention among high level modules for theservice of the same lower-level module (which maybe particularly important if the radio needs to supportoperation over several standards at the same time).We hope to address these important issues in the nearfuture.R EFERENCES[1] J. Palicot, C. Roland, Y. Louet, and A. Al Ghouwayel,“A new parameterization technique for reconfigurable radio:the common operator approach.” Submitted to Annales desTelecommunications, 2006.[2] C. Moy, J. Palicot, V. Rodriguez, and D. Giri, “Optimal deter-mination of common operators for multi-standards software-defined radio,” in  Proc. of 4th Karlsruhe Workshop on Software Radios , (Karlsruhe, Germany), March 2006. Forthcoming.[3] J. Palicot and C. Roland, “FFT: a basic function for a recon-figurable receiver,”  Proc. of IEEE ITC  , vol. 1, pp. 898– 902,Mar 2003.[4] B. Heyne and J. Goetze, “A pure CORDIC based FFT for re-configurable digital signal processing,” in  12th European Sig-nal Processing Conference (Eusipco2004) , September 2004.[5] A. Al Ghouwayel, Y. Louët, and J. Palicot, “A reconfigurablebutterfly architecture for Fourier and Fermat transforms,” in Proc. of 4th Karlsruhe Workshop on Software Radios , (Karl-sruhe, Germany), March 2006. Forthcoming.[6] H. Wang, T. Cai, and J. Song, “Analysis of common structureand software download for software defined radio,”  Proc. of  IEEE ICCT  , vol. 2, pp. 1112–1116, 2000.[7] F. Jondral, “Parametrization - a technique for SDR Implemen-tation,” in  Software Defined Radio - Enabling Technologies (W. Tuttlebee, ed.), pp. 233 – 256, London: John Wiley &Sons, 2002.[8] A.-R. Rhiemeier, “Benefits and limits of parameterized channelcoding for software radio,” in  Proc. of 2nd Karlsruhe Work-shop on Software Radios , (Karlsruhe, Germany), Mar 2002.[9] U. S. Jha, “Object oriented HW functions accelerate commu-nication, computing, and multimedia convergence,”  Proc. of  IEEE PIMRC  , September 2005.[10] W. Tuttlebee, “Software-defined radio: facets of a developingtechnology,”  IEEE Personal Communications , vol. 6, no. 2,pp. 38–44, 1999.[11] J. Belzile, S. Bernier, and M. Uhm, “Software radio modemsenter the SoC era,”  COTS Journal , September 2004.
Recommended
View more...
We Need Your Support
Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

Thanks to everyone for your continued support.

No, Thanks