@article {17980,
	title = {A Low-Overhead Asynchronous Interconnection Network for GALS Chip Multiprocessors},
	journal = {Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on},
	volume = {30},
	year = {2011},
	month = {2011/04//},
	pages = {494 - 507},
	abstract = {A new asynchronous interconnection network is introduced for globally-asynchronous locally-synchronous (GALS) chip multiprocessors. The network eliminates the need for global clock distribution, and can interface multiple synchronous timing domains operating at unrelated clock rates. In particular, two new highly-concurrent asynchronous components are introduced which provide simple routing and arbitration/merge functions. Post-layout simulations in identical commercial 90 nm technology indicate that comparable recent synchronous router nodes have 5.6-10.7 more energy per packet and 2.8-6.4 greater area than the new asynchronous nodes. Under random traffic, the network provides significantly lower latency and identical throughput over the entire operating range of the 800 MHz network and through mid-range traffic rates for the 1.36 GHz network, but with degradation at higher traffic rates. Preliminary evaluations are also presented for a mixed-timing (GALS) network in a shared-memory parallel architecture, running both random traffic and parallel benchmark kernels, as well as directions for further improvement.},
	keywords = {1.36, 800, 90, architecture;size, architectures;shared, asynchronous, benchmark, chip, chips;multiprocessor, distribution, distribution;frequency, GALS, GHz;frequency, interconnection, kernel;post-layout, layout;clock, locally-synchronous, memory, MHz;globally-asynchronous, multiple, multiprocessor;clock, multiprocessor;interface, network;mixed-timing, network;network, networks;microprocessor, networks;network, nm;circuit, Parallel, routing;network-on-chip;parallel, routing;parallel, simulation;random, synchronous, systems;, timing;low-overhead, traffic;shared-memory},
	isbn = {0278-0070},
	doi = {10.1109/TCAD.2011.2114970},
	author = {Horak,M.N. and Nowick,S.M. and Carlberg,M. and Vishkin, Uzi}
}
@conference {17979,
	title = {Toolchain for Programming, Simulating and Studying the XMT Many-Core Architecture},
	booktitle = {Parallel and Distributed Processing Workshops and Phd Forum (IPDPSW), 2011 IEEE International Symposium on},
	year = {2011},
	month = {2011/05//},
	pages = {1282 - 1291},
	abstract = {The Explicit Multi-Threading (XMT) is a general-purpose many-core computing platform, with the vision of a 1000-core chip that is easy to program but does not compromise on performance. This paper presents a publicly available tool chain for XMT, complete with a highly configurable cycle-accurate simulator and an optimizing compiler. The XMT tool chain has matured and has been validated to a point where its description merits publication. In particular, research and experimentation enabled by the tool chain played a central role in supporting the ease-of-programming and performance aspects of the XMT architecture. The compiler and the simulator are also important milestones for an efficient programmer{\textquoteright}s workflow from PRAM algorithms to programs that run on the shared memory XMT hardware. This workflow is a key component in accomplishing the dual goal of ease-of-programming and performance. The applicability of our tool chain extends beyond specific XMT choices. It can be used to explore the much greater design space of shared memory many-cores by system researchers or by programmers. As the tool chain can practically run on any computer, it provides a supportive environment for teaching parallel algorithmic thinking with a programming component. Unobstructed by techniques such as decomposition-first and programming for locality, this environment may be useful in deferring the teaching of these techniques, when desired, to more advanced or platform-specific courses.},
	keywords = {algorithm;XMT, architecture;XMT, architectures;shared, chain;cycle-accurate, compiler;programmer, compilers;parallel, component;shared, computing;optimizing, hardware;shared, many-core, many-core;concurrency, memory, multithreading;general-purpose, PRAM, simulator;ease-of-programming;explicit, systems;, theory;multi-threading;optimising, tool, workflow;programming, XMT},
	doi = {10.1109/IPDPS.2011.270},
	author = {Keceli,F. and Tzannes,A. and Caragea,G.C. and Barua,R. and Vishkin, Uzi}
}
@conference {15005,
	title = {Optimization of linked list prefix computations on multithreaded GPUs using CUDA},
	booktitle = {Parallel Distributed Processing (IPDPS), 2010 IEEE International Symposium on},
	year = {2010},
	month = {2010/04//},
	pages = {1 - 8},
	abstract = {We present a number of optimization techniques to compute prefix sums on linked lists and implement them on multithreaded GPUs using CUDA. Prefix computations on linked structures involve in general highly irregular fine grain memory accesses that are typical of many computations on linked lists, trees, and graphs. While the current generation of GPUs provides substantial computational power and extremely high bandwidth memory accesses, they may appear at first to be primarily geared toward streamed, highly data parallel computations. In this paper, we introduce an optimized multithreaded GPU algorithm for prefix computations through a randomization process that reduces the problem to a large number of fine-grain computations. We map these fine-grain computations onto multithreaded GPUs in such a way that the processing cost per element is shown to be close to the best possible. Our experimental results show scalability for list sizes ranging from 1M nodes to 256M nodes, and significantly improve on the recently published parallel implementations of list ranking, including implementations on the Cell Processor, the MTA-8, and the NVIDIA GeForce 200 series. They also compare favorably to the performance of the best known CUDA algorithm for the scan operation on the Tesla C1060.},
	keywords = {200, accesses;fine, accesses;linked, Bandwidth, C1060;cell, computations;extremely, computations;multithreaded, CUDA;MTA;NVIDIA, GeForce, GPUs;optimization;prefix, grain, high, list, memory, Parallel, prefix, process;coprocessors;multi-threading;, processor;data, series;Tesla, sums;randomization},
	doi = {10.1109/IPDPS.2010.5470455},
	author = {Wei, Zheng and JaJa, Joseph F.}
}
@conference {15104,
	title = {Overcoming the Hole in the Bucket: Public-Key Cryptography Resilient to Continual Memory Leakage},
	booktitle = {Foundations of Computer Science (FOCS), 2010 51st Annual IEEE Symposium on},
	year = {2010},
	month = {2010/10//},
	pages = {501 - 510},
	abstract = {In recent years, there has been a major effort to design cryptographic schemes that remain secure even when arbitrary information about the secret key is leaked (e.g., via side-channel attacks). We explore the possibility of achieving security under emphcontinual leakage from the emphentire secret key by designing schemes in which the secret key is updated over time. In this model, we construct public-key encryption schemes, digital signatures, and identity-based encryption schemes that remain secure even if an attacker can leak a constant fraction of the secret memory (including the secret key) in each time period between key updates. We also consider attackers who may probe the secret memory during the updates themselves. We stress that we allow unrestricted leakage, without the assumption that {\textquotedblleft}only computation leaks information{\textquotedblright}. Prior to this work, constructions of public-key encryption schemes secure under continual leakage were not known even under this assumption.},
	keywords = {continual, cryptography;, cryptography;public-key, encryption, key, key;digital, leakage;cryptographic, memory, schemes;digital, schemes;public-key, schemes;secret, signatures;identity-based, signatures;public},
	doi = {10.1109/FOCS.2010.55},
	author = {Brakerski,Z. and Kalai,Y.T. and Katz, Jonathan and Vaikuntanathan,V.}
}
@conference {14951,
	title = {Component-based Data Layout for Efficient Slicing of Very Large Multidimensional Volumetric Data},
	booktitle = {Scientific and Statistical Database Management, 2007. SSBDM {\textquoteright}07. 19th International Conference on},
	year = {2007},
	month = {2007/07//},
	pages = {8 - 8},
	abstract = {In this paper, we introduce a new efficient data layout scheme to efficiently handle out-of-core axis-aligned slicing queries of very large multidimensional volumetric data. Slicing is a very useful dimension reduction tool that removes or reduces occlusion problems in visualizing 3D/4D volumetric data sets and that enables fast visual exploration of such data sets. We show that the data layouts based on typical space-filling curves are not optimal for the out-of-core slicing queries and present a novel component-based data layout scheme for a specialized problem domain, in which it is only required to provide fast slicing at every k-th value, for any k gt; 1. Our component-based data layout scheme provides much faster processing time for any axis-aligned slicing direction at every k-th value, k gt; 1, requiring less cache memory size and without any replication of data. In addition, the data layout can be generalized to any high dimension.},
	keywords = {axis-aligned, cache, curves;very, data, data;data, databases;, handling;query, large, layout;data, memory, multidimensional, processing;very, queries;space-filling, size;component-based, slicing, slicing;out-of-core, volumetric},
	doi = {10.1109/SSDBM.2007.7},
	author = {Kim,Jusub and JaJa, Joseph F.}
}
@article {15038,
	title = {The block distributed memory model},
	journal = {Parallel and Distributed Systems, IEEE Transactions on},
	volume = {7},
	year = {1996},
	month = {1996/08//},
	pages = {830 - 840},
	abstract = {We introduce a computation model for developing and analyzing parallel algorithms on distributed memory machines. The model allows the design of algorithms using a single address space and does not assume any particular interconnection topology. We capture performance by incorporating a cost measure for interprocessor communication induced by remote memory accesses. The cost measure includes parameters reflecting memory latency, communication bandwidth, and spatial locality. Our model allows the initial placement of the input data and pipelined prefetching. We use our model to develop parallel algorithms for various data rearrangement problems, load balancing, sorting, FFT, and matrix multiplication. We show that most of these algorithms achieve optimal or near optimal communication complexity while simultaneously guaranteeing an optimal speed-up in computational complexity. Ongoing experimental work in testing and evaluating these algorithms has thus far shown very promising results},
	keywords = {accesses;single, address, algorithms;performance, algorithms;performance;remote, allocation;sorting;, balancing;matrix, bandwidth;communication, communication;load, complexity;computation, complexity;computational, complexity;cost, complexity;distributed, distributed, evaluation;resource, FFT;block, Fourier, latency;parallel, locality;communication, machines;interconnection, measure;data, memory, model;communication, model;computational, multiplication;memory, multiplication;parallel, problems;distributed, rearrangement, space;sorting;spatial, systems;fast, topology;interprocessor, transforms;matrix},
	isbn = {1045-9219},
	doi = {10.1109/71.532114},
	author = {JaJa, Joseph F. and Ryu,Kwan Woo}
}
@conference {15016,
	title = {Practical parallel algorithms for dynamic data redistribution, median finding, and selection},
	booktitle = {Parallel Processing Symposium, 1996., Proceedings of IPPS {\textquoteright}96, The 10th International},
	year = {1996},
	month = {1996/04//},
	pages = {292 - 301},
	abstract = {A common statistical problem is that of finding the median element in a set of data. This paper presents a fast and portable parallel algorithm for finding the median given a set of elements distributed across a parallel machine. In fact, our algorithm solves the general selection problem that requires the determination of the element of rank i, for an arbitrarily given integer i. Practical algorithms needed by our selection algorithm for the dynamic redistribution of data are also discussed. Our general framework is a distributed memory programming model enhanced by a set of communication primitives. We use efficient techniques for distributing, coalescing, and load balancing data as well as efficient combinations of task and data parallelism. The algorithms have been coded in SPLIT-C and run on a variety of platforms, including the Thinking Machines CM-5, IBM SP-1 and SP-2, Gray Research T3D, Meiko Scientific CS-2, Intel Paragon, and workstation clusters. Our experimental results illustrate the scalability and efficiency of our algorithms across different platforms and improve upon all the related experimental results known to the authors},
	keywords = {algorithms;performance, algorithms;scalability;statistical, allocation;, balancing, clusters;distributed, CM-5;communication, CS-2;SPLIT-C;Thinking, data, data;median, evaluation;resource, finding;parallel, Gray, Machines, memory, model;dynamic, Paragon;Meiko, primitives;distributed, problem;workstation, Programming, redistribution;load, research, scientific, SP-1;Intel, systems;parallel, T3D;IBM},
	doi = {10.1109/IPPS.1996.508072},
	author = {Bader, D.A. and JaJa, Joseph F.}
}
@conference {15039,
	title = {The block distributed memory model for shared memory multiprocessors},
	booktitle = {Parallel Processing Symposium, 1994. Proceedings., Eighth International},
	year = {1994},
	month = {1994/04//},
	pages = {752 - 756},
	abstract = {Introduces a computation model for developing and analyzing parallel algorithms on distributed memory machines. The model allows the design of algorithms using a single address space and does not assume any particular interconnection topology. We capture performance by incorporating a cost measure for interprocessor communication induced by remote memory accesses. The cost measure includes parameters reflecting memory latency, communication bandwidth, and spatial locality. Our model allows the initial placement of the input data and pipelined prefetching. We use our model to develop parallel algorithms for various data rearrangement problems, load balancing, sorting, FFT, and matrix multiplication. We show that most of these algorithms achieve optimal or near optimal communication complexity while simultaneously guaranteeing an optimal speed-up in computational complexity},
	keywords = {accesses;shared, address, algebra;parallel, algorithms;performance, algorithms;performance;pipelined, allocation;shared, balancing;matrix, bandwidth;computation, block, Communication, communication;load, complexity;computational, complexity;cost, complexity;distributed, complexity;optimal, data, distributed, evaluation;resource, Fourier, latency;optimal, locality;communication, measure;data, memory, model;communication, model;computational, multiplication;memory, multiprocessors;single, placement;interprocessor, prefetching;remote, problems;fast, rearrangement, space;sorting;spatial, speedup;parallel, systems;fast, systems;sorting;, transforms;input, transforms;matrix},
	doi = {10.1109/IPPS.1994.288220},
	author = {JaJa, Joseph F. and Ryu,Kwan Woo}
}
@conference {14939,
	title = {An efficient parallel algorithm for channel routing},
	booktitle = {Computer Design: VLSI in Computers and Processors, 1990. ICCD {\textquoteright}90. Proceedings., 1990 IEEE International Conference on},
	year = {1990},
	month = {1990/09//},
	pages = {400 - 403},
	abstract = {The channel-routing of a set of multiterminal nets in the standard two-layer model is considered. The sequential algorithms based on the greedy strategy do not seem to be easily parallelizable. Proposed is an efficient parallel algorithm for routing channels with cyclic constraints. The algorithm runs in time <e1>O</e1>(<e1>n</e1><sup>2</sup>/<e1>p</e1>+log<sup>2</sup><e1>p</e1>), with <e1>p</e1> processors, on a shared memory parallel random access machine (PRAM) model where 1 les;<e1>p</e1> les;<e1>n</e1><sup>2</sup> radic; and <e1>n</e1> is the size of the input. An efficient adaptation of this algorithm on a Sequent Balance 21000 multiprocessor system is reported},
	keywords = {21000;channel, access, algorithm;sequential, algorithms;, algorithms;shared, balance, CAD;computational, complexity;parallel, Layout, machine;standard, memory, model;circuit, nets;parallel, Parallel, PRAM;Sequent, random, routing;multiprocessor, system;multiterminal, two-layer},
	doi = {10.1109/ICCD.1990.130261},
	author = {Krishnamurthy, S. and JaJa, Joseph F.}
}
