In wireless sensor networks (WSNs), conserving the nodes' energy is one the main motivations in designing the medium access control (MAC) layer protocols. A common approach is to allow the nodes to turn their radio modules off periodically according to certain schedules. The nodes that operate on a common schedule and located in a common physical area form a virtual cluster. The nodes in the cluster borders have more active period to maintain the connectivity between clusters, thus, have shorter life spans. This work proposes a scheme that enables cluster merging in a distributed environment to eliminate the problem. The proposed scheme uses the schedule offset, the time difference between the starts of the active periods in two schedules, as the criteria for deciding the direction of the merging. We evaluate the performance of the proposed protocol using a mathematical estimation and simulation. The result shows the proposed scheme has up to 50 times shorter convergence time and save up to 90% more energy during the merging process compared to the existing global schedule protocols.

Highly popular Web sites can suffer classical congestion collapse because of the ability of outgoing 'bursty' data to congest the server side link. Using the well known and recognized network simulator ns we look at the effect that this congestion collapse has on user perceived performance (UPP) of a simulated Web site. We developed a protocol overlay for HTTP/1.1 and a complementary distribution infrastructure to alleviate the effects of this congestion. Our protocol HTTP(P2P) shows promise for increasing the maximum load of Web sites during times of high and very high Web site load and link contention. In our simulated environment, HTTP(P2P) significantly decreases the time required for users to download the Web page they request. The protocol also distributes the redirected traffic over the network to reduce secondary transient network congestion.

Demonstrating our framework on a collection of scientific loop nests, we were able to reduce an average of 84% of cache misses in the optimizable loop nests. This work lays the groundwork for handling a wide range of optimizations through further study of solution patterns in the CME solution table.

With the ever-widening performance gap between processors and main memory, cache memory, which is used to bridge this gap, is becoming more and more significant. Caches work well for programs that exhibit sufficient locality. Other programs, however, have reference patterns that fail to exploit the cache, thereby suffering heavily from high memory latency. In order to get high cache efficiency and achieve good program performance, efficient memory accessing behavior is necessary. In fact, for many programs, program transformations or source-code changes can radically alter memory access patterns, significantly improving cache performance. Both hand-tuning and compiler optimization techniques are often used to transform codes to improve cache utilization. Unfortunately, cache conflicts are difficult to predict and estimate, precluding effective transformations. Hence, effective transformations require detailed knowledge about the frequency and causes of cache misses in the code. This article describes methods for generating and solving Cache Miss Equations (CMEs) that give a detailed representation of cache behavior, including conflict misses, in loop-oriented scientific code. Implemented within the SUIF compiler framework, our approach extends traditional compiler reuse analysis to generate linear Diophantine equations that summarize each loop's memory behavior. While solving these equations is in general difficult, we show that is also unnecessary, as mathematical techniques for manipulating Diophantine equations allow us to relatively easily compute and/or reduce the number of possible solutions, where each solution corresponds to a potential cache miss. The mathematical precision of CMEs allows us to find true optimal solutions for transformations such as blocking or padding. The generality of CMEs also allows us to reason about interactions between transformations applied in concert. The article also gives examples of their use to determine array padding and offset amounts that minimize cache misses, and to determine optimal blocking factors for tiled code. Overall, these equations represent an analysis framework that offers the generality and precision needed for detailed compiler optimizations.

Analyzing and optimizing program memory performance is a pressing problem in high-performance computer architec-tures. Currently, software solutions addressing the processor-memory performance gap include compiler- or programmer-applied optimizations like data structure padding, matrix blocking, and other program transformations. Compiler op-timization can be effective, but the lack of precise analysis and optimization frameworks makes it impossible to confi-dently make optimal, rather than heuristic-based, program transformations. Imprecision is most problematic in situa-tions where hard-to-predict cache conflicts foil heuristic ap-proaches. Furthermore, the lack of a general framework for compiler memory performance analysis makes it impossi-ble to understand the combined effects of several program transformations. The Cache Miss Equation (CME) framework discussed in this paper addresses these issues. We express memory ref-erence and cache conflict behavior in terms of sets of equa-tions. The mathematical precision of CMEs allows us to find true optimal solutions for transformations like block-ing or padding. The generality of CMEs also allows us to reason about interactions between transformations applied in concert. Unlike our prior work, this framework applies to caches of arbitrary associativity. This paper also demon-strates the utility of CMEs by presenting precise algorithms for intra-variable padding, inter-variable padding, and se-lecting tile sizes. Our experiences with CMEs implemented in the SUIF system show that they are a unifying mathemat-ical framework offering the generality and precision impera-tive for compiler optimizations on current high-performance architectures. 1

Article Free Access Share on Cache miss equations: an analytical representation of cache misses Authors: Somnath Ghosh Department of Electrical Engineering, Princeton University Department of Electrical Engineering, Princeton UniversityView Profile , Margaret Martonosi Department of Electrical Engineering, Princeton University Department of Electrical Engineering, Princeton UniversityView Profile , Sharad Malik Department of Electrical Engineering, Princeton University Department of Electrical Engineering, Princeton UniversityView Profile Authors Info & Claims ICS '97: Proceedings of the 11th international conference on SupercomputingJuly 1997 Pages 317–324https://doi.org/10.1145/263580.263657Online:11 July 1997Publication History 144citation1,052DownloadsMetricsTotal Citations144Total Downloads1,052Last 12 Months48Last 6 weeks14 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