OpenRaiser/Intern-Atlas huggingface dataset:
Design of a Virtual Component Neutral Network-on-Chip Transaction Layer
Venue: arXiv cs.AR 2007
Year: 2007

Research studies have demonstrated the feasibility and advantages of Network-on-Chip (NoC) over traditional bus-based architectures but have not focused on compatibility communication standards. This paper describes a number of issues faced when designing a VC-neutral NoC, i.e. compatible with standards such as AHB 2.0, AXI, VCI, OCP, and various other proprietary protocols, and how a layered approach to communication helps solve these issues.
Model Reuse through Hardware Design Patterns
Venue: arXiv cs.SE 2007
Year: 2007

Increasing reuse opportunities is a well-known problem for software designers as well as for hardware designers. Nonetheless, current software and hardware engineering practices have embraced different approaches to this problem. Software designs are usually modelled after a set of proven solutions to recurrent problems called design patterns. This approach differs from the component-based reuse usually found in hardware designs: design patterns do not specify unnecessary implementation details. Several authors have already proposed translating structural design patterns concepts to hardware design. In this paper we extend the discussion to behavioural design patterns. Specifically, we describe how the hardware version of the Iterator can be used to enhance model reuse.
Exploiting Dynamic Workload Variation in Low Energy Preemptive Task Scheduling
Venue: arXiv cs.OH 2007
Year: 2007

A novel energy reduction strategy to maximally exploit the dynamic workload variation is proposed for the offline voltage scheduling of preemptive systems. The idea is to construct a fully-preemptive schedule that leads to minimum energy consumption when the tasks take on approximately the average execution cycles yet still guarantees no deadline violation during the worst-case scenario. End-time for each sub-instance of the tasks obtained from the schedule is used for the on-line dynamic voltage scaling (DVS) of the tasks. For the tasks that normally require a small number of cycles but occasionally a large number of cycles to complete, such a schedule provides more opportunities for slack utilization and hence results in larger energy saving. The concept is realized by formulating the problem as a Non-Linear Programming (NLP) optimization problem. Experimental results show that, by using the proposed scheme, the total energy consumption at runtime is reduced by as high as 60% for randomly generated task sets when comparing with the static scheduling approach only using worst case workload.
Rapid Generation of Thermal-Safe Test Schedules
Venue: arXiv cs.OH 2007
Year: 2007

Overheating has been acknowledged as a major issue in testing complex SOCs. Several power constrained system-level DFT solutions (power constrained test scheduling) have recently been proposed to tackle this problem. However, as it will be shown in this paper, imposing a chip-level maximum power constraint doesn't necessarily avoid local overheating due to the non-uniform distribution of power across the chip. This paper proposes a new approach for dealing with overheating during test, by embedding thermal awareness into test scheduling. The proposed approach facilitates rapid generation of thermal-safer test schedules without requiring time-consuming thermal simulations. This is achieved by employing a low-complexity test session thermal model used to guide the test schedule generation algorithm. This approach reduces the chances of a design re-spin due to potential overheating during test.
Modeling of a Reconfigurable OFDM IP Block Family For an RF System Simulator
Venue: arXiv cs.AR 2007
Year: 2007

The idea of design domain specific Mother Model of IP block family as a base of modeling of system integration is presented here. A common reconfigurable Mother Model for ten different standardized digital OFDM transmitters has been developed. By means of a set of parameters, the mother model can be reconfigured to any of the ten selected standards. So far the applicability of the proposed reconfiguration and analog-digital co-modeling methods have been proved by modeling the function of the digital parts of three, 802.11a, ADSL and DRM, transmitters in an RF system simulator. The model is intended to be used as signal source template in RF system simulations. The concept is not restricted to signal sources, it can be applied to any IP block development. The idea of the Mother Model will be applied in other design domains to prove that in certain application areas, OFDM transceivers in this case, the design process can progress simultaneously in different design domains - mixed signal, system and RTL-architectural - without the need of high-level synthesis. Only the Mother Models of three design domains are needed to be formally proved to function as specified.
C Based Hardware Design for Wireless Applications
Venue: arXiv cs.AR 2007
Year: 2007

The algorithms used in wireless applications are increasingly more sophisticated and consequently more challenging to implement in hardware. Traditional design flows require developing the micro architecture, coding the RTL, and verifying the generated RTL against the original functional C or MATLAB specification. This paper describes a C-based design flow that is well suited for the hardware implementation of DSP algorithms commonly found in wireless applications. The C design flow relies on guided synthesis to generate the RTL directly from the untimed C algorithm. The specifics of the C-based design flow are described using a simple DSP filtering algorithm consisting of a forward adaptive equalizer, a 64-QAM slicer and an adaptive decision feedback equalizer. The example illustrates some of the capabilities and advantages offered by this flow.
System Level Analysis of the Bluetooth Standard
Venue: arXiv cs.OH 2007
Year: 2007

The SystemC modules of the Link Manager Layer and Baseband Layer have been designed in this work at behavioral level to analyze the performances of the Bluetooth standard. In particular the probability of the creation of a piconet in presence of noise in the channel and the power reduction using the sniff and hold mode have been investigated.
AutoMoDe - Model-Based Development of Automotive Software
Venue: arXiv cs.SE 2007
Year: 2007

This paper describes first results from the AutoMoDe (Automotive Model-Based Development) project. The overall goal of the project is to develop an integrated methodology for model-based development of automotive control software, based on problem-specific design notations with an explicit formal foundation. Based on the existing AutoFOCUS framework, a tool prototype is being developed in order to illustrate and validate the key elements of our approach.
A Partitioning Methodology for Accelerating Applications in Hybrid Reconfigurable Platforms
Venue: arXiv cs.AR 2007
Year: 2007

In this paper, we propose a methodology for partitioning and mapping computational intensive applications in reconfigurable hardware blocks of different granularity. A generic hybrid reconfigurable architecture is considered so as the methodology can be applicable to a large number of heterogeneous reconfigurable platforms. The methodology mainly consists of two stages, the analysis and the mapping of the application onto fine and coarse-grain hardware resources. A prototype framework consisting of analysis, partitioning and mapping tools has been also developed. For the coarse-grain reconfigurable hardware, we use our previous-developed high-performance coarse-grain data-path. In this work, the methodology is validated using two real-world applications, an OFDM transmitter and a JPEG encoder. In the case of the OFDM transmitter, a maximum clock cycles decrease of 82% relative to the ones in an all fine-grain mapping solution is achieved. The corresponding performance improvement for the JPEG is 43%.
WWW Spiders: an introduction
Venue: arXiv cs.CY 2007
Year: 2007

In recent years, the study of complex networks has received a lot of attention. Real systems have gained importance in scientific publications, despite of an important drawback: the difficulty of retrieving and manage such great quantity of information. This paper wants to be an introduction to the construction of spiders and scrapers: specifically, how to program and deploy safely these kind of software applications. The aim is to show how software can be prepared to automatically surf the net and retrieve information for the user with high efficiency and safety.
Rate-Constrained Wireless Networks with Fading Channels: Interference-Limited and Noise-Limited Regimes
Venue: arXiv cs.IT 2007
Year: 2007

A network of $n$ wireless communication links is considered in a Rayleigh fading environment. It is assumed that each link can be active and transmit with a constant power $P$ or remain silent. The objective is to maximize the number of active links such that each active link can transmit with a constant rate $λ$. An upper bound is derived that shows the number of active links scales at most like $\frac{1}λ \log n$. To obtain a lower bound, a decentralized link activation strategy is described and analyzed. It is shown that for small values of $λ$, the number of supported links by this strategy meets the upper bound; however, as $λ$ grows, this number becomes far below the upper bound. To shrink the gap between the upper bound and the achievability result, a modified link activation strategy is proposed and analyzed based on some results from random graph theory. It is shown that this modified strategy performs very close to the optimum. Specifically, this strategy is \emph{asymptotically almost surely} optimum when $λ$ approaches $\infty$ or 0. It turns out the optimality results are obtained in an interference-limited regime. It is demonstrated that, by proper selection of the algorithm parameters, the proposed scheme also allows the network to operate in a noise-limited regime in which the transmission rates can be adjusted by the transmission powers. The price for this flexibility is a decrease in the throughput scaling law by a multiplicative factor of $\log \log n$.
Risk Minimization and Optimal Derivative Design in a Principal Agent Game
Venue: arXiv cs.CE 2007
Year: 2007

We consider the problem of Adverse Selection and optimal derivative design within a Principal-Agent framework. The principal's income is exposed to non-hedgeable risk factors arising, for instance, from weather or climate phenomena. She evaluates her risk using a coherent and law invariant risk measure and tries minimize her exposure by selling derivative securities on her income to individual agents. The agents have mean-variance preferences with heterogeneous risk aversion coefficients. An agent's degree of risk aversion is private information and hidden to the principal who only knows the overall distribution. We show that the principal's risk minimization problem has a solution and illustrate the effects of risk transfer on her income by means of two specific examples. Our model extends earlier work of Barrieu and El Karoui (2005) and Carlier, Ekeland and Touzi (2007).
Code Similarity on High Level Programs
Venue: arXiv cs.CV 2007
Year: 2007

This paper presents a new approach for code similarity on High Level programs. Our technique is based on Fast Dynamic Time Warping, that builds a warp path or points relation with local restrictions. The source code is represented into Time Series using the operators inside programming languages that makes possible the comparison. This makes possible subsequence detection that represent similar code instructions. In contrast with other code similarity algorithms, we do not make features extraction. The experiments show that two source codes are similar when their respective Time Series are similar.
Grassmannian Beamforming for MIMO Amplify-and-Forward Relaying
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, we derive the optimal transmitter/ receiver beamforming vectors and relay weighting matrix for the multiple-input multiple-output amplify-and-forward relay channel. The analysis is accomplished in two steps. In the first step, the direct link between the transmitter (Tx) and receiver (Rx) is ignored and we show that the transmitter and the relay should map their signals to the strongest right singular vectors of the Tx-relay and relay-Rx channels. Based on the distributions of these vectors for independent identically distributed (i.i.d.) Rayleigh channels, the Grassmannian codebooks are used for quantizing and sending back the channel information to the transmitter and the relay. The simulation results show that even a few number of bits can considerably increase the link reliability in terms of bit error rate. For the second step, the direct link is considered in the problem model and we derive the optimization problem that identifies the optimal Tx beamforming vector. For the i.i.d Rayleigh channels, we show that the solution to this problem is uniformly distributed on the unit sphere and we justify the appropriateness of the Grassmannian codebook (for determining the optimal beamforming vector), both analytically and by simulation. Finally, a modified quantizing scheme is presented which introduces a negligible degradation in the system performance but significantly reduces the required number of feedback bits.
Stability analysis of a max-min fair Rate Control Protocol (RCP) in a small buffer regime
Venue: arXiv cs.NI 2007
Year: 2007

In this note we analyse various stability properties of the max-min fair Rate Control Protocol (RCP) operating with small buffers. We first tackle the issue of stability for networks with arbitrary topologies. We prove that the max-min fair RCP fluid model is globally stable in the absence of propagation delays, and also derive a set of conditions for local stability when arbitrary heterogeneous propagation delays are present. The network delay stability result assumes that, at equilibrium, there is only one bottleneck link along each route. Lastly, in the simpler setting of a single link, single delay model, we investigate the impact of the loss of local stability via a Hopf bifurcation.
Declarative Diagnosis of Floundering
Venue: arXiv cs.PL 2007
Year: 2007

Many logic programming languages have delay primitives which allow coroutining. This introduces a class of bug symptoms -- computations can flounder when they are intended to succeed or finitely fail. For concurrent logic programs this is normally called deadlock. Similarly, constraint logic programs can fail to invoke certain constraint solvers because variables are insufficiently instantiated or constrained. Diagnosing such faults has received relatively little attention to date. Since delay primitives affect the procedural but not the declarative view of programs, it may be expected that debugging would have to consider the often complex details of interleaved execution. However, recent work on semantics has suggested an alternative approach. In this paper we show how the declarative debugging paradigm can be used to diagnose unexpected floundering, insulating the user from the complexities of the execution. Keywords: logic programming, coroutining, delay, debugging, floundering, deadlock, constraints
A Tutorial on Spectral Clustering
Venue: arXiv cs.DS 2007
Year: 2007

In recent years, spectral clustering has become one of the most popular modern clustering algorithms. It is simple to implement, can be solved efficiently by standard linear algebra software, and very often outperforms traditional clustering algorithms such as the k-means algorithm. On the first glance spectral clustering appears slightly mysterious, and it is not obvious to see why it works at all and what it really does. The goal of this tutorial is to give some intuition on those questions. We describe different graph Laplacians and their basic properties, present the most common spectral clustering algorithms, and derive those algorithms from scratch by several different approaches. Advantages and disadvantages of the different spectral clustering algorithms are discussed.
Faster Algorithms for Online Topological Ordering
Venue: arXiv cs.DS 2007
Year: 2007

We present two algorithms for maintaining the topological order of a directed acyclic graph with n vertices, under an online edge insertion sequence of m edges. Efficient algorithms for online topological ordering have many applications, including online cycle detection, which is to discover the first edge that introduces a cycle under an arbitrary sequence of edge insertions in a directed graph. In this paper we present efficient algorithms for the online topological ordering problem. We first present a simple algorithm with running time O(n^{5/2}) for the online topological ordering problem. This is the current fastest algorithm for this problem on dense graphs, i.e., when m > n^{5/3}. We then present an algorithm with running time O((m + nlog n)\sqrt{m}); this is more efficient for sparse graphs. Our results yield an improved upper bound of O(min(n^{5/2}, (m + nlog n)sqrt{m})) for the online topological ordering problem.
Managing Uncertainty: A Case for Probabilistic Grid Scheduling
Venue: arXiv cs.DC 2007
Year: 2007

The Grid technology is evolving into a global, service-orientated architecture, a universal platform for delivering future high demand computational services. Strong adoption of the Grid and the utility computing concept is leading to an increasing number of Grid installations running a wide range of applications of different size and complexity. In this paper we address the problem of elivering deadline/economy based scheduling in a heterogeneous application environment using statistical properties of job historical executions and its associated meta-data. This approach is motivated by a study of six-month computational load generated by Grid applications in a multi-purpose Grid cluster serving a community of twenty e-Science projects. The observed job statistics, resource utilisation and user behaviour is discussed in the context of management approaches and models most suitable for supporting a probabilistic and autonomous scheduling architecture.
Automatic Coding Rule Conformance Checking Using Logic Programs
Venue: arXiv cs.PL 2007
Year: 2007

Some approaches to increasing program reliability involve a disciplined use of programming languages so as to minimise the hazards introduced by error-prone features. This is realised by writing code that is constrained to a subset of the a priori admissible programs, and that, moreover, may use only a subset of the language. These subsets are determined by a collection of so-called coding rules.
Shannon Theoretic Limits on Noisy Compressive Sampling
Venue: arXiv cs.IT 2007
Year: 2007

In this paper, we study the number of measurements required to recover a sparse signal in ${\mathbb C}^M$ with $L$ non-zero coefficients from compressed samples in the presence of noise. For a number of different recovery criteria, we prove that $O(L)$ (an asymptotically linear multiple of $L$) measurements are necessary and sufficient if $L$ grows linearly as a function of $M$. This improves on the existing literature that is mostly focused on variants of a specific recovery algorithm based on convex programming, for which $O(L\log(M-L))$ measurements are required. We also show that $O(L\log(M-L))$ measurements are required in the sublinear regime ($L = o(M)$).
On the defence notion
Venue: arXiv cs.CR 2007
Year: 2007

'Trojan horses', 'logic bombs', 'armoured viruses' and 'cryptovirology' are terms recalling war gears. In fact, concepts of attack and defence drive the world of computer virology, which looks like a war universe in an information society. This war has several shapes, from invasions of a network by worms, to military and industrial espionage ...
Bounds on the Number of Iterations for Turbo-Like Ensembles over the Binary Erasure Channe
Venue: arXiv cs.IT 2007
Year: 2007

This paper provides simple lower bounds on the number of iterations which is required for successful message-passing decoding of some important families of graph-based code ensembles (including low-density parity-check codes and variations of repeat-accumulate codes). The transmission of the code ensembles is assumed to take place over a binary erasure channel, and the bounds refer to the asymptotic case where we let the block length tend to infinity. The simplicity of the bounds derived in this paper stems from the fact that they are easily evaluated and are expressed in terms of some basic parameters of the ensemble which include the fraction of degree-2 variable nodes, the target bit erasure probability and the gap between the channel capacity and the design rate of the ensemble. This paper demonstrates that the number of iterations which is required for successful message-passing decoding scales at least like the inverse of the gap (in rate) to capacity, provided that the fraction of degree-2 variable nodes of these turbo-like ensembles does not vanish (hence, the number of iterations becomes unbounded as the gap to capacity vanishes).
Considerations on P vs NP
Venue: arXiv cs.CC 2007
Year: 2007

In order to prove that the P of problems is different to the NP class, we consider the satisfability problem of propositional calculus formulae, which is an NP-complete problem. It is shown that, for every search algorithm A, there is a set E(A) containing propositional calculus formulae, each of which requires the algorithm A to take non-polynomial time to find the truth-values of its propositional letters satisfying it. Moreover, E(A)'s size is an exponential function of n, which makes it impossible to detect such formulae in a polynomial time. Hence, the satisfability problem does not have a polynomial complexity
Fair Scheduling in OFDMA-based Wireless Systems with QoS Constraints
Venue: arXiv cs.NI 2007
Year: 2007

In this work we consider the problem of downlink resource allocation for proportional fairness of long term received rates of data users and quality of service for real time sessions in an OFDMA-based wireless system. The base station allocates available power and bandwidth to individual users based on long term average received rates, QoS based rate constraints and channel conditions. We solve the underlying constrained optimization problem and propose an algorithm that achieves the optimal allocation. Numerical evaluation results show that the proposed algorithm provides better QoS to voice and video sessions while providing more and fair rates to data users in comparison with existing schemes.
Outage-Efficient Downlink Transmission Without Transmit Channel State Information
Venue: arXiv cs.IT 2007
Year: 2007

This paper investigates downlink transmission over a quasi-static fading Gaussian broadcast channel (BC), to model delay-sensitive applications over slowly time-varying fading channels. System performance is characterized by outage achievable rate regions. In contrast to most previous work, here the problem is studied under the key assumption that the transmitter only knows the probability distributions of the fading coefficients, but not their realizations. For scalar-input channels, two coding schemes are proposed. The first scheme is called blind dirty paper coding (B-DPC), which utilizes a robustness property of dirty paper coding to perform precoding at the transmitter. The second scheme is called statistical superposition coding (S-SC), in which each receiver adaptively performs successive decoding with the process statistically governed by the realized fading. Both B-DPC and S-SC schemes lead to the same outage achievable rate region, which always dominates that of time-sharing, irrespective of the particular fading distributions. The S-SC scheme can be extended to BCs with multiple transmit antennas.