Search

While considerable work has addressed the optimal AoI under different circumstances in single-hop networks, the exploration of AoI in multi-hop wireless networks is rarely attempted. More importantly, the inherent relationships between AoI and throughput are yet to be explored, especially in multi-hop networks. This paper studies AoI in multi-hop wireless networks and explores its potential relationships with throughput for the very first time, particularly focusing on the impacts of flexible routes on the two metrics, i.e., AoI and throughput. By developing a rigorous mathematical model with interference, channel allocation, link scheduling, and routing path selection taken into consideration, we build the interrelation between AoI and throughput in multi-hop networks. A multi-criteria optimization problem is formulated with the goal of simultaneously minimizing AoI and maximizing network throughput. By qualitatively analyzing their relationships, we exhibit that the two metrics may conflict with each other, implying the optimal solutions for the multi-criteria problem will include a set of Pareto-optimal points rather than a single point existing in the traditional optimization problem. We resort to a novel approach by transforming the multi-criteria problem into a single objective one so as to find the weakly Pareto-optimal points iteratively, thereby allowing us to screen all Pareto-optimal points for the solution. Through formal proof, our solution is demonstrated to be able to identify all Pareto-optimal points and terminate in a finite number of iterations. We conduct the simulation evaluation to identify the optimal tradeoff points of AoI and throughput, demonstrating that one performance metric may improve at the expense of degrading the other, with the routing path found as one of the key factors in determining such a tradeoff. [ABSTRACT FROM AUTHOR]

A bufferless network-on-chip (NoC) can deliver high energy efficiency, but such a NoC is subject to growing deflection when its traffic load rises. This article proposes Deflection Containment (DeC) for the bufferless NoC to address its notorious shortcomings of excessive deflection for performance improvement and energy savings. With multiple subnetworks bridged by an added link between two corresponding routers, DeC lets a contending flit in one subnetwork be forwarded to another subnetwork instead of deflected. Microarchitecture of DeC routers is rectified to shorten the critical path and lift network bandwidth. Its Cadence RTL implementations with a $15-nm$ 15 - n m process are conducted respectively for mesh-based NoCs and torus-based NoCs. Additionally, different sized DeC-NoCs are evaluated extensively and compared with previous bufferless designs (BLESS and MinBD), uncovering that DeC with two bridged subnetworks (dubbed DeC2) for 8X8 mesh-based NoCs can lower deflection drastically by some 90 percent and energy consumption by upto 51 percent under real benchmark traffic loads, in comparison to BLESS. Under various synthetic traffic models and workloads, 16X16 torus-based DeC2-NoC sustains up to 2.33X loads when compared with its mesh-based counterpart, exhibiting the same clock rate and taking only negligible more power and area according to our full layout results. [ABSTRACT FROM AUTHOR]

In multicore systems, a large portion of checkpoint time overhead can be hidden from the execution critical path by resorting to a dedicated checkpointing thread run concurrently with regular execution threads for compressing checkpoint files to lower checkpointing overhead. On the other hand, the restore time is on the critical path that cannot be hidden, making it most important to accelerate execution restore upon failures. This work pursues a restore-express (REX) strategy for multi-level checkpointing (MLC), applicable to any incremental checkpointing (IC). Oblivious to application codes, REX employs adaptive IC (AIC) for local (L1) checkpointing and follows our runtime control for second-level (L2) checkpointing, with its aim at express restore from failures while holding down the overall execution time. It takes advantage of two unique insights for overhead reduction: (1) the modified pages of an incremental checkpoint file are likely to exist in a subsequent checkpoint file, and (2) many data patterns (on an average, some 40 percent of them) stay unchanged from one L2 checkpoint file to the next. These insights enable REX to (1) coalesce IC files (by involving only the last copy of every dirty page among files) and (2) boost file compression across multiple L2 checkpoints. Time and storage overhead results of REX during normal job execution are gathered for 16 benchmarks from SPEC, PARSEC, and NPB suites. The evaluation outcomes of the execution restore time confirm that REX is fast and able to quicken restore by a factor of 4.5× when compared with its IC counterpart (without utilizing the unique insights), while incurring same execution time overhead. [ABSTRACT FROM AUTHOR]

Video streams, either in the form of Video On-Demand (VOD) or live streaming, usually have to be converted (i.e., transcoded) to match the characteristics of viewers’ devices (e.g., in terms of spatial resolution or supported formats). Transcoding is a computationally expensive and time-consuming operation. Therefore, streaming service providers have to store numerous transcoded versions of a given video to serve various display devices. With the sharp increase in video streaming, however, this approach is becoming cost-prohibitive. Given the fact that viewers’ access pattern to video streams follows a long tail distribution, for the video streams with low access rate, we propose to transcode them in an on-demand (i.e., lazy) manner using cloud computing services. The challenge in utilizing cloud services for on-demand video transcoding, however, is to maintain a robust QoS for viewers and cost-efficiency for streaming service providers. To address this challenge, in this paper, we present the Cloud-based Video Streaming Services (CVS2) architecture. It includes a QoS-aware scheduling component that maps transcoding tasks to the Virtual Machines (VMs) by considering the affinity of the transcoding tasks with the allocated heterogeneous VMs. To maintain robustness in the presence of varying streaming requests, the architecture includes a cost-efficient VM Provisioner component. The component provides a self-configurable cluster of heterogeneous VMs. The cluster is reconfigured dynamically to maintain the maximum affinity with the arriving workload. Simulation results obtained under diverse workload conditions demonstrate that CVS2 architecture can maintain a robust QoS for viewers while reducing the incurred cost of the streaming service provider by up to 85 percent. [ABSTRACT FROM AUTHOR]

To lower on-chip SRAM area overhead for chip multiprocessors (CMPs), this work treats a novel directory design which compresses present-bit vectors (PVs) by dropping “runs of zeros” commonly existing and lets PVs be transformed to their variations after sharer relinquishment for hashing alternative table sets to lift table utilization. Featured with relinquishment c oherence and compressed sharer t racking (ReCoST), the proposed design attains superior directory efficiency and maintains “exact” directory representations, as a result of dropping abound long runs of zeros present in PVs. According to full-system simulation using gem5 for a range of core counts under PARSEC benchmarks, ReCoST is found to enjoy 3.21 $\times$ (or 2.64$\times$ ) more efficiency in directory storage than conventional bit-tracking directories (or the best directory known so far, called SCD) for a 64-core CMP under monotasking (or multitasking) workloads while ensuring execution slowdowns to stay within 2.4 percent (or 3.3 percent). [ABSTRACT FROM AUTHOR]

Cloud computing users are most concerned about the application turnaround time and the monetary cost involved. For lower monetary costs, less expensive services, like spot instances offered by Amazon, are often made available, albeit to their relatively frequent resource unavailability that leads to on-going execution being evicted, thereby undercutting execution performance. Meanwhile, multithreaded applications may take advantage of elastic resource availability and cost fluctuation inherent to the systems. However, their potential gains on utilizing spot instances would be contingent upon how they handle resource unavailability, calling for an effective checkpointing. This work presents design and implementation of our enhanced adaptive incremental checkpointing (EAIC) for multithreaded applications on the RaaS clouds under spot instance pricing. EAIC model takes into account spot instance revocation events, besides hardware failures, for fast and accurately predicting the desirable points of time to take checkpoints so as to markedly reduce the expected job turnaround time and the monetary cost. The experimental results from our established test bed on PARSEC benchmarks under real spot instance price traces from Amazon EC2 show that EAIC lowers both the application turnaround time and the monetary cost markedly (by up to 58% and 59%, respectively) in comparison to its recent checkpointing counterpart. [ABSTRACT FROM AUTHOR]

Sand monitoring gives the benefits of avoiding equipment erosion and production failure in the oil industry. This paper presents the design and implementation of a reliable and cost-effective sand monitoring system for measuring sand production in gas and oil flows in real time. The designed monitoring system involves two acoustic emission (AE) sensors and one Doppler sensor for gauging the sand impaction and the velocity of sand particles in a nonintrusive manner, respectively. It is implemented on a field programmable gate array (FPGA) as a prototype for real-time data acquisition and processing, and evaluated using a testbed pump skid available in our laboratory. Relying on a low-cost FPGA board to integrate all acquisition and processing functionality, our monitoring system can measure the sand production amount on-the-fly reliably with high accuracy, according to our experimental evaluation. It is likely to achieve better accuracy than one without the Doppler sensor. The proposed monitoring system is affordable for wide deployment, given its high accuracy, good resilience to surrounding noise, and low cost (when compared with commercially available systems whose price tags can be some tenfold higher). [ABSTRACT FROM PUBLISHER]

This paper pursues RFID support for localization, aiming to pinpoint an object in 3D space. Given a set of RFID tags and/or readers deployed as reference points at known locations in a hexahedron (like shipping container or storage room), a passive and an active localization schemes are considered in this paper. Being the very first range-free 3D localization, our schemes depend solely on RFID tags and readers without other devices or sensors, and it avoids the need of distance estimation according to received wireless signal strength or phase difference. Our passive scheme locates an RFID tag attached to the target object, with both tags and readers as reference points. The active scheme locates an RFID reader, by iteratively determining a 3D sphere best covering the activated reference tags, referred to as the decision boundary optimization scheme (DeB). Results by simulations and testbed experiments using Alien RFID kits have been obtained, and they reveal that DeB outperforms its passive counterpart and achieves the localization error of 0.07 ft. Additionally, DeB yields better location accuracy and yet is much faster than a previous counterpart. With enhanced DeB (EDeB), accuracy of an object located near a hexahedron side or corner is improved considerably. [ABSTRACT FROM PUBLISHER]

We present a distinct longest prefix matching (LPM) lookup scheme able to achieve exceedingly concise lookup tables (CoLT), suitable for scalable routers. Based on unified hash tables for handling both IPv4 and IPv6 simultaneously, CoLT excels over previous mechanisms in: 1) lower on-chip storage for lookup tables; 2) simpler table formats to enjoy richer prefix aggregation and easier implementation; and 3) most importantly, deemed the only design able to accommodate both IPv4 and IPv6 addresses uniformly and effectively. As its hash tables permit multiple possible buckets to hold each prefix (following a migration rule to avoid false positives altogether), CoLT exhibits the best memory efficiency and can launch parallel search over tables during every LPM lookup, involving fewer cycles per lookup when on-chip memory is used to implement hash tables. With 16 (or 32) on-chip SRAM blocks clocked at 500 MHz (achievable in today's 65-nm technology), it takes 2 (or 1.6) cycles on average to complete a lookup, yielding 250 (or 310+) millions of packets per second (MPPS) mean throughput. Being hash-oriented, CoLT well supports incremental table updates, besides its high table utilization and lookup throughput. [ABSTRACT FROM PUBLISHER]

This paper deals with decentralized, QoS-aware middleware for checkpointing arrangement in Mobile Grid (MoG) computing systems. Checkpointing is more crucial in MoG systems than in their conventional wired counterparts due to host mobility, dynamicity, less reliable wireless links, frequent disconnections, and variations in mobile systems. We've determined the globally optimal checkpoint arrangement to be NP-complete and so consider Reliability Driven (ReD) middleware, employing decentralized QoS-aware heuristics, to construct superior checkpointing arrangements efficiently. With ReD, an MH (mobile host) simply sends its checkpointed data to one selected neighboring MH, and also serves as a stable point of storage for checkpointed data received from a single approved neighboring MH. ReD works to maximize the probability of checkpointed data recovery during job execution, increasing the likelihood that a distributed application, executed on the MoG, completes without sustaining an unrecoverable failure. It allows collaborative services to be offered practically and autonomously by the MoG. Simulations and actual testbed implementation show ReD's favorable recovery probabilities with respect to Random Checkpointing Arrangement (RCA) middleware, a QoS-blind comparison protocol producing random arbitrary checkpointing arrangements. [ABSTRACT FROM AUTHOR]

Introduces fast compaction through the use of active subcubes in a fragmented hypercube so as to produce a contiguous free region and eliminate the adverse impact of fragmentation on performance. Results of the compaction in a fragmented hypercube; Conclusion reached.

Proposes an efficient approach for identifying all the maximum complete subcube in a faulty hypercube. Features that help arrive at the general expression for incomplete subcubes; Methodology used to derive the expression of specifying subcubes which contain a given node; Introduces the process of finding incomplete subcubes; Provision of distributed identification of all maximum incomplete subcubes in a faulty hypercube.

States that mutual exclusion in shared-memory multiprocessors is realized by employing a lock to determine the processor among those which compete for the critical section. What could create heavy synchronization traffic/and or serious contention over the network, thereby degrading system performance considerably; Introduction of a efficient scheme which keep synchronization traffic low and avoids serious hot-spot contention.

Presents a paper which outlined how incomplete hypercubes with arbitrary nodes, can provide incremental flexibility in a complete hypercube system. Importance of simulation when analyzing incomplete hypercubes; Example of a routing algorithm for incomplete hypercubes; Examination of the characteristics of the incomplete hypercube.

Presents a description of an efficient procedure capable of determining all maximum fault-free subcubes in a faulty hypercube. Methodology for finding subcubes containing a given node; Prerequisites of reducing execution slowdown in a hypercube with given faults; Evidence supporting why the procedure can deal with node failures and link failures uniformly and equally efficiently.

Presents the consideration of speedy task migration in that two disjoint paths that are created between every pair of corresponding nodes for delivering migrated information simultaneously, reducing the size of data transmitted over a path. Node model and related work; Pertinent isomorphisms and path properties; Speedy task migration; Migration time analysis; Conclusion of the study.

Studies the efficient determination of maximum incomplete subcubes in hypercubes with faults. Time complexity; Reconfiguration of hypercubes with faulty nodes; Efficient algorithm; Properties of faulty cubes.

Packet classification is central to a wide array of Internet applications and services, with its approaches mostly involving either hardware support or optimization steps needed by software-oriented techniques (to add precomputed markers and insert rules in the search data structures). Unfortunately, an approach with hardware support is expensive and has limited scalability, whereas one with optimization fails to handle incremental rule updates effectively. This work deals with rapid packet classification, realized by hashing round-down prefixes (HaRP) in a way that the source and the destination IP prefixes specified in a rule are rounded down to “designated prefix lengths” (DPL) for indexing into hash sets. HaRP exhibits superb hash storage utilization, able to not only outperform those earlier software-oriented classification techniques but also well accommodate dynamic creation and deletion of rules. HaRP makes it possible to hold all its search data structures in the local cache of each core within a contemporary processor, dramatically elevating its classification performance. Empirical results measured on an AMD 4-way 2.8 GHz Opteron system (with 1 MB cache for each core) under six filter data sets (each with up to 30 K rules) obtained from a public source unveil that HaRP enjoys up to some 3.6\times throughput level achievable by the best known decision tree-based counterpart, HyperCuts (HC). [ABSTRACT FROM AUTHOR]