QR factorization is a ubiquitous operation in many engineering and scientific applications. In this paper, we present efficient realization of Householder Transform (HT) based QR factorization through algorithm-architecture co-design where we achieve performance improvement of 3-90x in-terms of Gflops/watt over state-of-the-art multicore, General Purpose Graphics Processing Units (GPGPUs), Field Programmable Gate Arrays (FPGAs), and ClearSpeed CSX700. Theoretical and experimental analysis of classical HT is performed for opportunities to exhibit higher degree of parallelism where parallelism is quantified as a number of parallel operations per level in the Directed Acyclic Graph (DAG) of the transform. Based on theoretical analysis of classical HT, an opportunity to re-arrange computations in the classical HT is identified that results in Modified HT (MHT) where it is shown that MHT exhibits 1.33x times higher parallelism than classical HT. Experiments in off-the-shelf multicore and General Purpose Graphics Processing Units (GPGPUs) for HT and MHT suggest that MHT is capable of achieving slightly better or equal performance compared to classical HT based QR factorization realizations in the optimized software packages for Dense Linear Algebra (DLA). We implement MHT on a customized platform for Dense Linear Algebra (DLA) and show that MHT achieves 1.3x better performance than native implementation of classical HT on the same accelerator. For custom realization of HT and MHT based QR factorization, we also identify macro operations in the DAGs of HT and MHT that are realized on a Reconfigurable Data-path (RDP). We also observe that due to re-arrangement in the computations in MHT, custom realization of MHT is capable of achieving 12 percent better performance improvement over multicore and GPGPUs than the performance improvement reported by General Matrix Multiplication (GEMM) over highly tuned DLA software packages for multicore and GPGPUs which is counter-intuitive.

In this paper we present design and analysis of scalable hardware architectures for training learning parameters of RBFNN to classify large data sets. We design scalable hardware architectures for K-means clustering algorithm to training the position of hidden nodes at hidden layer of RBFNN and pseudoinverse algorithm for weight adjustments at output layer. These scalable parallel pipelined architectures are capable of implementing data sets with no restriction on their dimensions. This paper also presents a flexible and scalable hardware accelerator for realization of classification using RBFNN, which puts no limitation on the dimension of the input data is developed. We report FPGA synthesis results of our implementations. We compare results of our hardware accelerator with CPU, GPU and implementations of the same algorithms and with other existing algorithms. Analysis of these results show that scalability of our hardware architecture makes it favorable solution for classification of very large data sets.

REDEFINE is a distributed dynamic dataflow architecture, designed for exploiting parallelism at various granularities as an embedded system-on-chip (SoC). This paper dwells on the flexibility of REDEFINE architecture and its execution model in accelerating real-time applications coupled with a WCET analyzer that computes execution time bounds of real time applications.

In this paper we present design and analysis of a scalable real-time Face Recognition (FR) module to perform 450 recognitions per second. We introduce an algorithm for FR, which is a combination of Weighted Modular Principle Component Analysis and Radial Basis Function Neural Networks. This algorithm offers better recognition accuracy in various practical conditions than algorithms used in existing architectures for real-time FR. To meet real-time requirements, a Scalable Parallel Pipelined Architecture (SPPA) is developed by realizing the above FR algorithm as independent parallel streams and sub-streams of computations. SPPA is capable of supporting large databases maintained in external (DDR) memory. By casting the computations in a stream into hardware, we present the design of a Scalable Unit for Region Evaluation (SURE) core. Using SURE cores as computer elements in a massively parallel CGRA, like REDFINE, we provide a FR system on REDEFINE called REFRESH. We report FPGA and ASIC synthesis results for SPPA and REFRESH. Through analysis using these results, we show that excellent scalability and added programmability in REFRESH makes it a flexible and favorable solution for real-time FR.

Advances in wireless internet, sensor technologies, mobile technologies, and global positioning technologies have renewed interest in location based services (LBSs) among mobile users. LBSs on smartphones allow consumers to locate nearby products and services, in exchange of their location information. Precision of location data helps for accurate query processing of LBSs but it may lead to severe security violations and several privacy threats, as intruders can easily determine user's common paths or actual locations. Encryption is the most explored approach for ensuring security. It can give protection against third party attacks but it cannot provide protection against privacy threats on the server which can still obtain user location and use it for malicious purposes. Location obfuscation is a technique to protect user privacy by altering the location of the users while preserving capability of server to compute few mathematical functions which are useful for the user over the obfuscated location information. This work mainly concentrates on LBSs which wants to know the distance travelled by user for providing their services and compares encryption and obfuscation techniques. This study proposes various methods of location obfuscation for GPS location data which are used to obfuscate user's path and location from service provider. Our work shows that user privacy can be maintained without affecting LBSs results, and without incurring significant overheads.

Givens Rotation is a key computation-intensive block in embedded wireless applications. In order to achieve an efficient mapping which smoothly scales to the underlying architecture, we propose two new Column-based Givens Rotation algorithms, derived from traditional Fast Givens and Square-root and Division Free Givens algorithms. These algorithms allow annihilation of multiple elements in a column of the input matrix simultaneously, without a dependency bottle-neck allowing increased parallelism, resource sharing and scalability. The ease of mapping and scalability has been tested on a layered coarse-grained reconfigurable architecture reaching close to optimal results for highly parallel architectures.

This paper presents two hardware architectures of bi-cubic convolution interpolation termed Parallelized Row Column Interpolation Architecture (PRCIA) and Serialized Row Column Interpolation Architecture (SRCIA) for real-time image scaling. These architectures factor in the challenges of high computational complexity, redundant computations and repeated memory accesses, which were otherwise not explicitly addressed in existing architectures. Besides, the proposed architectures also employ parallel computations to improve the throughput for realtime applications. The proposed architectures have been emulated and tested on Virtex-6 FPGA. The emulated PRCIA and SRCIA are able to scale input grayscale images of dimensions up to 640 × 480 at 59 and 48 frames per second respectively with arbitrary scaling factors up to 4 in both dimensions.

A new layered reconfigurable architecture is proposed which exploits modularity, scalability and flexibility to achieve high energy efficiency and memory bandwidth. Using two flavors of Column-wise Givens rotation, derived from traditional Fast Givens and Square root and Division Free Givens Rotation algorithms the architecture is thoroughly evaluated for scalability, speed, area and energy. Combining an efficient mapping strategy of the highly parallel algorithms capable of annihilation of multiple elements of a column of the input matrix and using the new features of the architecture, 9 architectural variants were explored achieving a clean trade-off of execution speed versus area, while keeping relatively constant energy.

Elasticity in cloud systems provides the flexibility to acquire and relinquish computing resources on demand. However, in current virtualized systems resource allocation is mostly static. Resources are allocated during VM instantiation and any change in workload leading to significant increase or decrease in resources is handled by VM migration. Hence, cloud users tend to characterize their workloads at a coarse grained level which potentially leads to under-utilized VM resources or under performing application. A more flexible and adaptive resource allocation mechanism would benefit variable workloads, such as those characterized by web servers. In this paper, we present an elastic resources framework for IaaS cloud layer that addresses this need. The framework provisions for application workload forecasting engine, that predicts at run-time the expected demand, which is input to the resource manager to modulate resource allocation based on the predicted demand. Based on the prediction errors, resources can be over-allocated or under-allocated as compared to the actual demand made by the application. Over-allocation leads to unused resources and under allocation could cause under performance. To strike a good trade-off between over-allocation and under-performance we derive an excess cost model. In this model excess resources allocated are captured as over-allocation cost and under-allocation is captured as a penalty cost for violating application service level agreement (SLA). Confidence interval for predicted workload is used to minimize this excess cost with minimal effect on SLA violations. An example case-study for an academic institute web server workload is presented. Using the confidence interval to minimize excess cost, we achieve significant reduction in resource allocation requirement while restricting application SLA violations to below 2-3%.

Cloud computing model separates usage from ownership in terms of control on resource provisioning. Resources in the cloud are projected as a service and are realized using various service models like IaaS, PaaS and SaaS. In IaaS model, end users get to use a VM whose capacity they can specify but not the placement on a specific host or with which other VMs it can be co-hosted. Typically, the placement decisions happen based on the goals like minimizing the number of physical hosts to support a given set of VMs by satisfying each VMs capacity requirement. However, the role of the VMM usage to support I/O specific workloads inside a VM can make this capacity requirement incomplete. I/O workloads inside VMs require substantial VMM CPU cycles to support their performance. As a result, placement algorithms need to include the VMM's usage on a per VM basis. Secondly, cloud centers encounter situations wherein change in existing VM's capacity or launching of new VMs need to be considered during different placement intervals. Usually, this change is handled by migrating existing VMs to meet the goal of optimal placement. We argue that VM migration is not a trivial task and does include loss of performance during migration. We quantify this migration overhead based on the VM's workload type and include the same in placement problem. One of the goals of the placement algorithm is to reduce the VM's migration prospects, thereby reducing chances of performance loss during migration. This paper evaluates the existing ILP and First Fit Decreasing (FFD) algorithms to consider these constraints to arrive at placement decisions. We observe that ILP algorithm yields optimal results but needs long computing time even with parallel version. However, FFD heuristics are much faster and scalable algorithms that generate a sub-optimal solution, as compared to ILP, but in time-scales that are useful in real-time decision making. We also observe that including VM migration overheads in the placement algorithm results in a marginal increase in the number of physical hosts but a significant, of about 84 percent reduction in VM migration.

In this paper we propose a fully parallel 64K point radix-44FFT processor. The radix-44parallel unrolled architecture uses a novel radix-4 butterfly unit which takes all four inputs in parallel and can selectively produce one out of the four outputs. The radix-44block can take all 256 inputs in parallel and can use the select control signals to generate one out of the 256 outputs. The resultant 64K point FFT processor shows significant reduction in intermediate memory but with increased hardware complexity. Compared to the state-of-art implementation [5], our architecture shows reduced latency with comparable throughput and area. The 64K point FFT architecture was synthesized using a 130nm CMOS technology which resulted in a throughput of 1.4 GSPS and latency of 47.7μs with a maximum clock frequency of 350MHz. When compared to [5], the latency is reduced by 303μs with 50.8% reduction in area.

Mapping applications onto a Coarse Grained Re-configurable Architecture (CGRA) requires knowledge about the interconnect topology used on the reconfigurable fabric. In order to make communication as efficient as possible, the application sub-structures or partitions need to be mapped to appropriate Compute Elements on the fabric, such that frequently communicating nodes are placed closer. In this paper, we present an interconnect-topology independent mapping algorithm to map applications onto a Coarse Grained Reconfigurable Architecture (CGRA). Our study has been carried out on a CGRA called REDEFINE. The mapping algorithm takes into account the communication serialization which occurs when two data transfers are assigned to the same communication link on the fabric. We extend the algorithm to also address reconfiguration overheads while performing the mapping. The resultant mapping algorithm performs 20% better on average than the mapping scheme based on Baba et al. scheme [1].

In Dynamically Reconfigurable Processors (DRPs), compilation involves breaking an application into sub-tasks for piecewise execution on the fabric. These sub-tasks are sequenced based on data and control dependences. In DRPs, sub-task prefetching is used to hide the reconfiguration time while another sub-task executes. In REDEFINE, our target DRP, subtasks are referred to as HyperOps. Determining the successor for a HyperOp requires merging information from the control flow graph and the HyperOp dataflow graph. Succession in many cases is data dependent. Since hardware branch predictors cannot be applied due to the non-binary branches, we employ a speculative prefetch unit together with a profile based prediction scheme. Simulation results show around 7-33% reduction in overall execution time, when compared to the execution time without prefetching. We observe better performance when fewer resources on the fabric are used to execute prefetched HyperOps.

This paper reports the design of an input-triggered polymorphic ASIC for H.264 baseline decoder. Hardware polymorphism is achieved by selectively reusing hardware resources at system and module level. Complete design is done using ESL design tools following a methodology that maintains consistency in testing and verification throughout the design flow. The proposed design can support frame sizes from QCIF to 1080p.

In this paper we explore an implementation of a high-throughput, streaming application on REDEFINE-v2, which is an enhancement of REDEFINE. REDEFINE is a polymorphic ASIC combining the flexibility of a programmable solution with the execution speed of an ASIC. In REDEFINE Compute Elements are arranged in an 8x8 grid connected via a Network on Chip (NoC) called RECONNECT, to realize the various macrofunctional blocks of an equivalent ASIC.

Modern wireline and wireless communication devices are multimode and multifunctional communication devices. In order to support multiple standards on a single platform, it is necessary to develop a reconfigurable architecture that can provide the required flexibility and performance. The channel decoder is one of the most compute intensive and essential elements of any communication system. Most of the standards require a reconfigurable channel decoder that is capable of performing Viterbi decoding and turbo decoding. Furthermore, the channel decoder needs to support different configurations of Viterbi and turbo decoders. In this paper, we propose a reconfigurable channel decoder that can be reconfigured for standards such as WCDMA, CDMA2000, IEEE802.11, DAB, DVB and GSM. Different parameters like code rate, constraint length, polynomials and truncation length can be configured to map any of the above mentioned standards. A multiprocessor approach has been followed to provide higher throughput and scalable power consumption in various configurations of the reconfigurable Viterbi decoder and turbo decoder. We have proposed a hybrid register exchange approach for multiprocessor architecture to minimize power consumption.

Emerging embedded applications are based on evolving standards (e.g., MPEG2/4, H.264/265, IEEE802.11a/b/g/n). Since most of these applications run on handheld devices, there is an increasing need for a single chip solution that can dynamically interoperate between different standards and their derivatives. In order to achieve high resource utilization and low power dissipation, we propose REDEFINE, a polymorphic ASIC in which specialized hardware units are replaced with basic hardware units that can create the same functionality by runtime re -composition. It is a “future-proof” custom hardware solution for multiple applications and their derivatives in a domain. In this article, we describe a compiler framework and supporting hardware comprising compute, storage, and communication resources. Applications described in high-level language (e.g., C) are compiled into application substructures. For each application substructure, a set of compute elements on the hardware are interconnected during runtime to form a pattern that closely matches the communication pattern of that particular application. The advantage is that the bounded CEs are neither processor cores nor logic elements as in FPGAs. Hence, REDEFINE offers the power and performance advantage of an ASIC and the hardware reconfigurability and programmability of that of an FPGA/instruction set processor. In addition, the hardware supports custom instruction pipelining. Existing instruction-set extensible processors determine a sequence of instructions that repeatedly occur within the application to create custom instructions at design time to speed up the execution of this sequence. We extend this scheme further, where a kernel is compiled into custom instructions that bear strong producer-consumer relationship (and not limited to frequently occurring sequences of instructions). Custom instructions, realized as hardware compositions effected at runtime, allow several instances of the same to be active in parallel. A key distinguishing factor in majority of the emerging embedded applications is stream processing. To reduce the overheads of data transfer between custom instructions, direct communication paths are employed among custom instructions. In this article, we present the overview of the hardware-aware compiler framework, which determines the NoC-aware schedule of transports of the data exchanged between the custom instructions on the interconnect. The results for the FFT kernel indicate a 25% reduction in the number of loads/stores, and throughput improves by log(n) for n-point FFT when compared to sequential implementation. Overall, REDEFINE offers flexibility and a runtime reconfigurability at the expense of 1.16× in power and 8× in area when compared to an ASIC. REDEFINE implementation consumes 0.1× the power of an FPGA implementation. In addition, the configuration overhead of the FPGA implementation is 1,000× more than that of REDEFINE.

Run-time interoperability between different applications based on H.264/AVC is an emerging need in networked infotainment, where media delivery must match the desired resolution and quality of the end terminals. In this paper, we describe the architecture and design of a polymorphic ASIC to support this. The H.264 decoding flow is partitioned into modules, such that the polymorphic ASIC meets the design goals of low-power, low-area, high flexibility, high throughput and fast interoperability between different profiles and levels of H.264. We demonstrate the idea with a multi-mode decoder that can decode baseline, main and high profile H.264 streams and can interoperate at run.time across these profiles. The decoder is capable of processing frame sizes of up to 1024×768 at 30 fps. The design synthesized with UMC 0.13μm technology, occupies 250k gates and runs at 100MHz.

Application accelerators are predominantly ASICs. The cost of ASIC solutions are order of magnitudes higher than programmable processing cores. Despite this, ASIC solutions are preferred when both high performance and low power is the target. ASICs offer no flexibility in terms of it being able to cater to application derivatives, unless this has been provisioned for at the time of design. In this paper we define the architecture of Runtime Reconfigurable Hardware (RRH) as the platform for application acceleration. The proposed RRH is a homogeneous fabric comprising computing, storage and communicating resources. We also propose a synthesis methodology to realize application written a high level language (HLL) on the RRH. Applications described in HLL is compiled into application substructures. For each application substructure a set of Compute Elements interconnected in a manner that closely matches the communication pattern within it, is allocated. CEs in such a configuration is called a hardware affine. Hardware Affines are carved out on the RRH at runtime. These hardware affines are defined at compile time, and are provisioned at runtime on the fabric. By virtue of the fact that these hardware affines are NOT instruction set processor cores or Logic Elements as in FPGAs, we bear the performance and power advantage of an ASIC, and the hardware reconfigurability/programmability of that of an FPGA/Instruction Set Processor.

A polymorphic ASIC is a runtime reconfigurable hardware substrate comprising compute and communication elements. It is a “future proof” custom hardware solution for multiple applications and their derivatives in a domain. Interoperability between application derivatives at runtime is achieved through hardware reconfiguration. In this paper we present the design of a single cycle Network on Chip (NoC) router that is responsible for effecting runtime reconfiguration of the hardware substrate. The router design is optimized to avoid FIFO buffers at the input port and loop back at output crossbar. It provides virtual channels to emulate a non-blocking network and supports a simple X-Y relative addressing scheme to limit the control overhead to 9 bits per packet. The 8×8 honeycomb NoC (RECONNECT) implemented in 130nm UMC CMOS standard cell library operates at 500MHz and has a bisection bandwidth of 28.5GBps. The network is characterized for random, self-similar and application specific traffic patterns that model the execution of multimedia and DSP kernels with varying network loads and virtual channels. Our implementation with 4 virtual channels has an average network latency of 24 clock cycles and throughput of 62.5% of the network capacity for random traffic. For application specific traffic the latency is 6 clock cycles and throughput is 87% of the network capacity.

In modern wireline and wireless communication systems, Viterbi decoder is one of the most compute intensive and essential elements. Each standard requires a different configuration of Viterbi decoder. Hence there is a need to design a flexible reconfigurable Viterbi decoder to support different configurations on a single platform. In this paper we present a reconfigurable Viterbi decoder which can be reconfigured for standards such as WCDMA, CDMA2000, IEEE 802.11, DAB, DVB, and GSM. Different parameters like code rate, constraint length, polynomials and truncation length can be configured to map any of the above mentioned standards. Our design provides higher throughput and scalable power consumption in various configuration of the reconfigurable Viterbi decoder. The power and throughput can also be optimized for different standards.

Aggressive superscalar processor with deep pipeline and sophisticated speculative execution techniques is pushing the power budget to its limit. It is found that a significant portion of this power is wasted during wrong path execution and non power optimal allocation of power hungry resources. Dynamic reconfiguration of micro-architectural resources can be exploited to bring down this waste at runtime. Lack of architectural method to capture the behavior of a program at runtime makes dynamic reconfiguration a challenge. In this paper we propose a method to characterize program behavior at runtime using conflict miss pattern of a data cache, which in turn identifies different program phases in terms of cache utilization. We use this phase information to enable/disable cache ways dynamically depending on the conflict miss pattern of a program. Using a hardware tracking mechanism we ensure that the program performance (throughput in terms of IPC) does not degrade beyond a tolerable limit. Through simulation we establish that an average improvement of 32% (best case 38%) in cache power saving is achieved at the expense of less than 2% degradation in performance for SPEC-CPU and MEDIA benchmarks. The additional hardware that detects and captures the phase information is outside the critical path of the processor and does not contribute to the overall delay.

In this paper we propose the architecture of a SoC fabric onto which applications described in a HLL are synthesized. The fabric is a homogeneous layout of computation, storage and communication resources on silicon. Through a process of composition of resources (as opposed to decomposition of applications), application specific computational structures are defined on the fabric at runtime to realize different modules of the applications in hardware. Applications synthesized on this fabric offers performance comparable to ASICs while retaining the programmability of processing cores. We outline the application synthesis methodology through examples, and compare our results with software implementations on traditional platforms with unbounded resources.

Pervasive computing aims at providing computation ubiquitously and a means of realizing anytime, anywhere computing. Pervasive computing is characterized by an infrastructure that enables execution of task (application) that demand automated, continual and multiple unobtrusive services in heterogeneous environments. They use invisible and ubiquitously distributed computational devices. Therefore pervasive computing requires a common single integrated programming solution that would facilitate proactive real-time collaborations among devices, software agents and execution of task. Such systems often termed as loosely coupled systems greatly benefit from service oriented architecture that allows software systems to provide services to end-user applications or other services through published and discoverable interfaces. One of the main issues in loosely coupled systems is the QoS. It is defined as how well a service is satisfied. QoS in such systems is application specific and is multidimensional. We identify two important issues in guaranteeing QoS in such systems: i) The infrastructure should decompose the application specific QoS parameters of multiple tasks (applications) executing in pervasive computing environment into set of QoS parameters and map them to distinct components of task execution, ii) Guaranteeing the QoS parameters with constraints in resource limited pervasive environments. In this paper we propose a framework for guaranteeing QoS by identifying two levels of agreement (service level and resource level) by the middleware entity. This entity identifies the QoS parameters from applications and forms distinct sets applicable to components involved in execution of task. Our aim is develop a generalized architecture that provides a platform for identifying QoS requirements of the applications, mapping these requirements in terms of service level agreements and resource level agreements. Finally , we propose a framework for monitoring and using system level parameters.

H.264 video standard achieves high quality video along with high data compression when compared to other existing video standards. H.264 uses context-based adaptive variable length coding (CAVLC) to code residual data in baseline profile. In this paper, the authors describe a novel architecture for CAVLC decoder, including coeff_token decoder, level decoder, total_zeros decoder and run_before decoder. UMC library in 0.13mu CMOS technology is used to synthesize the proposed design. The proposed design reduces chip area and improves critical path performance of CAVLC decoder in comparison with (Chang et al., 2005). Macroblock level (including luma and chroma) pipeline processing for CAVLC is implemented with an average of 141 cycles (including pipeline buffering) per macroblock at 250MHz clock frequency. To compare our results with (Chang et al., 2005) clock frequency is constrained to 125MHz. The area required for the proposed architecture is 17586 gates, which is 22.1% improvement in comparison to (Chang et al., 2005). The authors obtain a throughput of 1.73 * 106macroblocks/second, which is 28% higher than that reported in [1]. The proposed design meets the processing requirement of 1080HD video at 30frames/seconds

The growth of high-performance application in computer graphics, signal processing and scientific computing is a key driver for high performance, fixed latency, pipelined floating point dividers. Solutions available in the literature use large lookup table for double precision floating point operations. In this paper, we propose a cost effective, fixed latency pipelined divider using modified Taylor-series expansion for double precision floating point operations. We reduce chip area by using a smaller lookup table. We show that the latency of the proposed divider is 49.4 times the latency of a full-adder. The proposed divider reduces chip area by about 81% than the pipelined divider in (Jong-Chul Jeong, 2004) which is based on modified Taylor-series

Ad hoc networks are being used in applications ranging from disaster recovery to distributed collaborative entertainment applications. Ad hoc networks have become one of the most attractive solution for rapid deployment of interconnecting large number of mobile personal devices. The user community of mobile personal devices are demanding a variety of value added multimedia entertainment services. The popularity of peer group is increasing and one or some members of the peer group need to send data to some or all members of the peer group. The increasing demand for group oriented value added services is driving for efficient multicast service over ad hoc networks. Access control mechanisms need to be deployed to provide guarantee that the unauthorized users cannot access the multicast content. In this paper, we present a topology aware key management and distribution scheme for secure overlay multicast over MANET to address node mobility related issues for multicast key management. We use overlay approach for key distribution and our objective is to keep communication overhead low for key management and distribution. We also incorporate reliability using explicit acknowledgments with the key distribution scheme. Through simulations we show that the proposed key management scheme has low communication overhead for rekeying and improves the reliability of key distribution.

CMPs enable simultaneous execution of multiple applications on the same platforms that share cache resources. Diversity in the cache access patterns of these simultaneously executing applications can potentially trigger inter-application interference, leading to cache pollution. Whereas a large cache can ameliorate this problem, the issues of larger power consumption with increasing cache size, amplified at sub-100nm technologies, makes this solution prohibitive. In this paper, in order to address the issues relating to power-aware performance of caches, we propose a caching structure that addresses the following: 1) Definition of application-specific cache partitions as an aggregation of caching units (molecules). The parameters of each molecule namely size, associativity and line size are chosen so that the power consumed by it and access time are optimal for the given technology. 2) Application-specific resizing of cache partitions with variable and adaptive associativity per cache line, way size and variable line size. 3) A replacement policy that is transparent to the partition in terms of size, heterogeneity in associativity and line size. Through simulation studies we establish the superiority of molecular cache (caches built as aggregations of molecules) that offers a 29% power advantage over that of an equivalently performing traditional cache

Streaming video is a key functionality in Internet based services such as distant education, VoD etc. The high bandwidth requirements associated with such applications coupled with limited I/O bandwidth of the server limits the throughput levels achieved by these systems. Such systems can largely benefit if the abundant resources such as storage and bandwidth available at the end systems (otherwise called as peers) are put to use. Availability of streaming service is largely affected by the transient nature of the peers. Therefore, we identify two important issues in these systems, viz (i) scalability, (in terms of support large number of clients) (ii) high data availability (minimizing the loss of segments due to the transience of peers). In this paper we propose a throughput driven, highly available 'streaming stored video' service architecture over a peer-to-peer network. We use distributed caching scheme where the initial segments of data are temporarily cached and served to subsequent requests, thereby reducing the number of requests to the server. We exploit the inherent redundancy of FEC based channel coding to provide high availability. Our aim is to show that despite this high transience of peers, the proposed distributed caching scheme helps reduce the number of server streams requested and provide high data availability, while serving large community of clients. We describe our three-tier architecture to realize the proposed model and measure the potential of our scheme in terms of increase in overall system capacity.

We propose a clock-domain-based partitioning technique for practicing scan test in large system-on-chips with multiple clock domains with the intent of reducing test application time and test power.

Streaming live video over peers in the Internet is gaining popularity since it has the advantage of reducing the load on the server and enable the server to perform other specialized services more effectively. It also helps reduce the server bandwidth and is therefore no more a limiting factor for the number of clients served. We propose a architecture for 'streaming stored video' over peer-to-peer network. While a given peer continues to receive segments of the stream, simultaneously caching these segments locally renders this peer to inturn act as a source for other peers. These peers are highly transient in nature and the exit of a peer from the network results in loss of video segments. We overcome this in our architecture by exploiting the inherent redundancy of FEC encoding of video streams. Through simulations we establish the novelty of our architecture and show that our proposed solution incurs minimum overhead on the peers and does not increase the playback latency much more than the jitter buffer latency.

Streaming live video over peers in the Internet is gaining popularity since it has the advantage of reducing the load on the server and enable the server to perform other specialized services more effectively. Further it reduces the server bandwidth and is therefore no longer a limiting factor for the number of clients served. A architecture for streaming stored video over peer-to-peer network is proposed in this paper. While a given peer continues to receive segments of the stream, simultaneously caching these segments locally renders this peer to in turn act as a source for other peers. These peers are highly transient in nature and the exit of a peer from the network results in loss of video segments and overcomes this in our architecture by exploiting the inherent redundancy of FEC channel coding of video streams. Through simulations the novelty of our architecture and show that our proposed solution incurs minimum overhead on the peers and does not increase the playback latency much more than the jitter buffer latency is established.

In this paper, we argue that the address space of memory regions that participate in inter task communication is over-specified by the traditional communication models used in behavioral modeling, resulting in sub-optimal implementations. We propose shared messaging communication model and the associated channels for efficient inter task communication of high bandwidth data streams in behavioral models of signal processing applications. In shared messaging model, tasks communicate data through special memory regions whose address space is unspecified by the model without introducing non determinism. Address space to these regions can be assigned during mapping of application to specific architecture, by exploring feasible alternatives. We present experimental results to show that this flexibility reduces the complexity (e.g., communication latency, memory usage) of implementations significantly (up to an order of magnitude).

Multivoltage scheduling (MVS) for datapaths offers the energy savings of voltage scaling on a per-operation basis with a voltage aware operator scheduling. This work investigates the effect of using multivoltage register file storage in operator graph scheduling for multivoltage datapaths, thus partitioning the variable storage space on the basis of operating voltages. Scheduling operations on multivoltage functional units lowers the energy-delay product by exploiting slack in the schedule. We find that using multivoltage partitioned register files do the same by exploiting the variable lifetimes in the schedule. In a resource constrained context, longer variable lifetimes provide the opportunity to store such variables in low voltage register files. A ZOLP formulation for the resource constrained MVS problem is presented along with energy-delay savings obtained from applying this formulation to image processing transform graphs.

VLIW processors are statically scheduled processors and their performance depends on the quality of schedules generated by the compiler's scheduler. We propose a new scheduling scheme where the application is first divided into decision trees and then further split into traces. Traces are speculatively scheduled on the processor based on their probability of execution. We have developed a tool "SpliTree" to generate traces automatically. By using dynamic branch prediction for scheduling traces our scheme achieves approximately 1.4/spl times/ performance improvement over that using decision trees for Spec92 benchmarks simulated on TriMedia/spl trade/.

In this paper we describe an area efficient power minimization scheme “Control Generated Clocking I‘ that saves significant amounts of power in datapath registers and clock drivers of sequential circuits. Power savings are achieved by making simple changes to the state machines controlling the datapath. These changes enable the control signals from the state machines themselves to be used as clocks for the datapath registers. Use of these control generated clocks makes the static timing analysis of designs implementing this scheme simpler when compared to techniques such as clock gating. This scheme preserves the cycle boundaries on which registers load data, thereby allowing reuse of functional test cases developed for the original circuit. In this paper we also describe timing requirements of a design in which this scheme has been implemented, cost-benefit aspects of this scheme and an algorithm for the automatic synthesis of control generated clocks. Results from application of this technique on a\ncomplex design are then discussed.\n

In this paper, we present an architecture framework called SYMPHONY consisting of a linear array of processors that exploits parallelism in media applications at micro (ILP) and macro (threads) levels. High speed communication and synchronization necessary for efficient multitheading is achieved using novel hardware and software mechanisms. We demonstrate the efficacy of the SYMPHONY framework by performance evaluation of an instance in the framework. We show that multithreaded architectures coupled with SIMD parallelism provides performance improvement in excess of 2/spl times/ over conventional superscalar architectures.

Clock gating is an effective technique for minimizing dynamic power in sequential circuits. However, clock gating has some practical difficulties viz., possibility of glitches on the gated clock and in use of static timing analysis for verifying timing of the design. In this paper we describe a robust scheme for power minimization that eliminates these difficulties of clock gating and yet provides nearly the same power savings. This scheme does not rely on propagation delays in the circuit for functioning, and is robust across process technologies. In this scheme, the controllers sequencing operations in a datapath are modified so that the control signals themselves are used as clocks for registers in the datapath. Since these "control clocks" typically operate at lower frequencies, power is saved in the registers and in the clock drivers. This scheme also preserves the cycle boundaries on which registers in the original circuit load data, thereby allowing reuse of test cases developed for the functional verification of the original circuit.

Although tree multipliers result in good logic depth, they are not amenable to dense VLSI implementation due to the complexity of wiring. We address the issue of optimal partial product reduction for parallel tree multipliers. An algorithm is developed to trade-off wiring complexity with logic depth. An automatic generator is developed to generate a netlist for any size multiplier with optimized placement information. This netlist with placement information is taken through a datapath place and route tool to create a compact layout for the generated multipliers. The results indicate that the performance of the generated multipliers in terms of speed can be similar to custom designed multipliers.

Presents a method to explore the design space of multi-threaded architectures using PAMELA (PerformAnce ModEling LAnguage). The domain of applications we consider is digital signal processing (DSP), where high performance is derived by exploiting both fine-grain and coarse-grain parallelism in the application. The modeling scheme takes an unified view of both fine-grain and coarse-grain parallelism in a given application to measure the performance of the architecture. The application-written using a high-level language-is compiled, and a trace generated for benchmark data in terms of the instruction set architecture of the processor. The generated trace is for a single uni-threaded, uni-processor system. This trace is pre-processed and re-targeted to generate multi-threaded architecture-specific PAMELA code. Using a material-oriented approach, the resulting PAMELA code is executed to evaluate various architecture options over the entire design space iteratively, subject to implementation constraints. We demonstrate the suitability and simplicity of the approach with an example.

The interest in low bitrate video coding has increased considerably with the creation of new applications and services requiring this class of bitrate in their function. In this paper we explore techniques for compression of image sequences in a manner that optimizes the results for the human receiver. We propose a new motion estimator using two novel block match algorithms which are based on human perception. Simulations with image sequences have shown an improved bitrate while maintaining "image quality" when compared to conventional motion estimation techniques using the MAD block match criteria.

Wave pipelining is a design technique for increasing the throughput of a digital circuit or system without introducing pipelining registers between adjacent combinational logic blocks in the circuit/system. However, this requires balancing of the delays along all the paths from the input to the output which comes the way of its implementation. Static CMOS is inherently susceptible to delay variation with input data, and hence, receives a low priority for wave pipelined digital design. On the other hand, ECL and CML, which are amenable to wave pipelining, lack the compactness and low power attributes of CMOS. In this paper we attempt to exploit wave pipelining in CMOS technology. We use a single generic building block in Normal Process Complementary Pass Transistor Logic (NPCPL), modeled after CPL, to achieve equal delay along all the propagation paths in the logic structure. An 8/spl times/8 b multiplier is designed using this logic in a 0.8 /spl mu/m technology. The carry-save multiplier architecture is modified suitably to support wave pipelining, viz., the logic depth of all the paths are made identical. The 1 mm/spl times/0.6 mm multiplier core supports a throughput of 400 MHz and dissipates a total power of 0.6 W. We develop simple enhancements to the NPCPL building blocks that allow the multiplier to sustain throughputs in excess of 600 MHz. The methodology can be extended to introduce wave pipelining in other circuits as well.>

Article Free Access Share on Architectural synthesis of performance-driven multipliers with accumulator interleaving Authors: Debabrata Ghosh View Profile , S. K. Nandy View Profile , P. Sadayappan View Profile , K. Parthasarathy View Profile Authors Info & Claims DAC '93: Proceedings of the 30th international Design Automation ConferenceJuly 1993 Pages 303–307https://doi.org/10.1145/157485.164902Online:01 July 1993Publication History 2citation206DownloadsMetricsTotal Citations2Total Downloads206Last 12 Months1Last 6 weeks0 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We attempt to exploit wave pipelining in CMOS technology. We use Normal Process Complementary Pass Transistor Logic (NPCPL) which is modeled after CPL, to achieve equal delay along all the propagation paths in the logic structure. An 8/spl times/8-bit multiplier is designed using this logic in a 0.8 /spl mu/ technology. The carry-save multiplier architecture is modified suitably to support wave pipelining, viz., the logic depth of all the paths are made identical. The 1 mm/spl times/0.6 mm multiplier core supports a throughput of 400 MHz and dissipates a total power of 0.8 W. The methodology can be extended to introduce wave pipelining in other circuits as well.>

In this paper we develop a multithreaded VLSI processor linear array architecture to render complex environments based on the radiosity approach. The processing elements are identical and multithreaded. They work in Single Program Multiple Data (SPMD) mode. A new algorithm to do the radiosity computations based on the progressive refinement approach[2] is proposed. Simulation results indicate that the architecture is latency tolerant and scalable. It is shown that a linear array of 128 uni-threaded processing elements sustains a throughput close to 0.4 million patches/sec.

In this paper we propose algorithms for performing DRC on a bitmapped layout and develop special purpose architecture for its implementation. We Use window scan method, with flexible window size, reduce redundant pixel processing in a window unlike that in [5].

The Quad-CIF tree has been proposed as a data structure for hierarchical design of VLSI. Frequently encountered operations in VLSI design require a lot of search effort on a Quad-CIF tree. Additionally, since the empty spaces are not explicitly stored in the tree, layout compaction is difficult to achieve. To support such operations efficiently, we propose a dual quadtree structure for VLSI design. At the first level we represent a cell in the layout as a “painted quadtree”. The painted quadtree stores the entire region spanned by all the rectangles in the cell. Once the cell is designed it is stored in the form of boundary codes. At the second level of the dual structure, these boundary codes are stored in a Quad-CIF tree. Therefore, the dual structure affords us the convenience of using the painted quadtree for interactive design and the excellent features of the Quad-CIF tree for hierarchical design and compact storage representation.