Transactional memory (TM) has been proposed to alleviate some key programmability problems in chip multiprocessors. Most TMs optimistically allow concurrent transactions, detecting read-write or write-write conflicts. Upon conflicts, existing hardware TMs (HTMs) use one of three conflict-resolution policies: (1) always-abort, (2) always-wait for some conflicting transactions to complete, or (3) always-go past conflicts and resolve acyclic conflicts at commit or abort upon cyclic dependencies. While each policy has advantages, the policies degrade performance under contention by limiting concurrency (always-abort, always-wait) or incurring late aborts due to cyclic dependencies (always-go). Thus, while always-go avoids acyclic aborts, no policy avoids cyclic aborts. We propose Wait-n-GoTM (WnGTM) to increase concurrency while avoiding cyclic aborts. We observe that most cyclic dependencies are caused by threads interleaving multiple accesses to a few heavily-read-write-shared delinquent data cache blocks. These accesses occur in code sections called cycle inducer sections (CISTs). Accordingly, we propose Wait-n-Go (WnG) conflict-resolution to avoid many cyclic aborts by predicting and serializing the CISTs. To support the WnG policy, we extend previous HTMs to (1) allow multiple readers and writers, (2) scalably identify dependencies, and (3) detect cyclic dependencies via new mechanisms, namely, conflict transactional state, order-capture, and hardware timestamps, respectively. In 16-core simulations of STAMP, WnGTM achieves average speedups of 46% for higher-contention benchmarks and 28% for all benchmarks over always-abort (TokenTM) with low-contention benchmarks remaining unchanged, compared to always-go (DATM) and always-wait (LogTM-SE), which perform worse than and 6% better than TokenTM, respectively.

Transactional memory (TM) has been proposed to address some of the programmability issues of chip multiprocessors. Hardware implementations of transactional memory (HTMs) have made significant progress in providing support for features such as long transactions that spill out of the cache, and context switches, page and thread migration in the middle of transactions. While essential for the adoption of HTMs in real products, supporting these features has resulted in significant state overhead. For instance, TokenTM adds at least 16 bits per block in the caches which is significant in absolute terms, and steals 16 of 64 (25%) memory ECC bits per block, weakening error protection. Also, the state bits nearly double the tag array size. These significant and practical concerns may impede the adoption of HTMs, squandering the progress achieved by HTMs. The overhead comes from tracking the thread identifier and the transactional read-sharer count at the Ll-block granularity. The thread identifier is used to identify the transaction, if only one, to which an Ll-evicted block belongs. The read-sharer count is used to identify conflicts involving multiple readers (i.e., write to a block with non-zero count). To reduce this overhead, we observe that the thread identifiers and read-sharer counts are not needed in a majority of cases. (1) Repeated misses to the same blocks are rare within a transaction (i.e., locality holds). (2) Transactional read-shared blocks that both are evicted from multiple sharers' Lis and are involved in conflicts are rare. Exploiting these observations, we propose a novel HTM, called LiteTM, which completely eliminates the count and identifier and uses software to infer the lost information. Using simulations of the STAMP benchmarks running on 8 cores, we show that LiteTM reduces TokenTM's state overhead by about 87% while performing within 4%, on average, and 10%, in the worst case, of TokenTM.

As chip multiprocessors scale the number of on chip cores, the superior scalability of multihop networks compared to buses and crossbars makes multihop networks the choice interconnection strategy. However, a significant part of the networks' energy is consumed in the buffers used to handle link contention via back pressured routing. Recent work proposes to apply well-known backpressure less routing techniques, which eliminate buffers, and hence buffer power(static and dynamic), at the cost of some misrouting/dropping upon link contention (misrouted/dropped flits are eventually recovered/retransmitted). At low loads, misrouting (dropping)is rare and hence backpressure less routing performs well. Unfortunately, backpressure less routers incur significant misrouting/dropping under high loads and saturate at lower throughputs than back pressured networks, resulting in poorer performance and energy. We make the key observation that because load varies significantly across applications, back pressureless and back pressured networks are not robust in performance-energy across the spectrum of high and low loads. That is, at high loads backpressure less networks suffer considerable performance and energy disadvantage compared to back pressured networks, and the energy disadvantage reverse sat low loads. To address this robustness issue, we propose a novel adaptive flow control (AFC) router which dynamically adapts between back pressured and backpressure less flow control. AFC employs three novel mechanisms, namely local contention thresholds, gossip-induced mode-switch, and lazy VCallocation. The first mechanism maximizes performance (and minimizes energy) in the common case, and the second mechanism ensures correctness in corner cases. The third mechanism exploits flit-by-flit routing in AFC's back pressured mode to simplify VC allocation and reduces the buffer requirements by a factor of two in AFC's back pressured mode. Simulations using commercial workloads and SPLASH-2 confirm AFC'srobustness by showing that AFC achieves performance and energy that are closer to that of the better of backpressure and backpressure less networks.

The email volume per mailbox has largely remained low and unchanged in the past several decades, and hence mail server performance has largely remained a secondary issue. The steep rise in the amount of unsolicited emails, i.e. spam, in the past decade, however, has permanently disrupted this tranquility of largely steady email volume and turned mail server performance into an increasingly important issue. In this paper, we point out that modern mail servers were not originally designed with email spam in mind, and as such, as the "common case'' workload for mail servers has shifted from legitimate emails to spam emails, we argue it is time to revisit mail server architecture design in following the system design principle of optimizing the common case. In particular, we show how to optimize the performance of three major components of modern mail servers, the concurrency architecture, the disk I/O, and DNSBL lookups, by exploiting the new "common case" workload. An evaluation of our prototype implementation of the enhanced postfix architecture shows that the optimizations significantly reduce the CPU, disk, and network resource consumptions, and improves the throughput of the mail server by 18% under a university departmental mail server workload and by 40% under a spam sinkhole workload.

We present a hierarchical method for segmenting text areas in natural images. The method assumes that the text is written with a contrasting color on a more or less uniform background. No assumption is made regarding the language or character set used to write the text. In particular, the text can contain simple graphics or symbols. The key feature of our approach is that we first concentrate on finding the background of the text, before testing whether there is actually text on the background. Since uniform areas are easy to find in natural images, and since text backgrounds define areas which contain "holes" (where the text is written) we thus look for uniform areas containing "holes" and label them as text backgrounds candidates. Each candidate area is then further tested for the presence of text within its convex hull. We tested our method on a database of 65 images including English and Urdu text. The method correctly segmented all the text areas in 63 of these images, and in only 4 of these were areas that do not contain text also segmented.

A major task of a wireless sensor network is energy-efficient, timely, and robust dissemination of sensor readings back to the sink node. The AIDA project [1] aims to create a new sensor network architecture, that uses antenna arrays of the distributed sensor nodes to create directional radio waves that can reach order-of-magnitude farther than individual antennas of the sensor nodes. This new network architecture, based on collaborative beamforming, drastically changes many aspects of the conventional networking stack. As part of the AIDA project, we are designing new energyefficient MAC and routing protocols for the new, distributed beamforming physical layer, which effectively involves “manysensors-to-many-sensors” for a single data packet transmission. 1. BACKGROUND

A digital watermark is an undetectable mark placed on a host media. There are various applications for digital watermarks which include authentication, finger printing and digital rights enforcement. This implies that the watermark should be tolerant to image processing and lossy compression type of operations. Most standard watermarking techniques do not survive wavelet based compression and may also not be compatible with the scalability feature of wavelet based compression. We present a novel digital watermarking scheme which can successfully withstand wavelet based compression, as well as standard watermark attacks. Our technique is designed to work along side the SNR scalable transmission feature provided with most wavelet compression suites so that the watermark may be authenticated at any level of SNR transmission. Experimental results show that our proposed watermarking method performs better than existing techniques when the host data is compressed using wavelet transforms.