Extending the BSP model for multi-core and out-of-core computing: MBSP

We present an extension of the bulk-synchronous parallel (BSP) model to abstract and model parallelism in the presence of multiple memory hierarchies and multiple cores. We call the new model MBSP for multi-memory BSP. The BSP model has been used to model internal memory parallel computers; MBSP retains the properties of BSP and in addition can abstract not only traditional external memory-supported parallelism (e.g. that uses another level of slower memory) but also multi-level cache-based memory hierarchies such as those present in multi-core systems. Present day multi-core systems are limited parallelism architectures with fast inter-core communication but limited fast memory availability. Abstracting the programming requirements of such architectures in a useful and usable manner is the objective of introducing MBSP. We propose multi-core program and algorithm design that measures resource utilization through a septuplet $(p\text{,}l\text{,}g\text{,}m\text{,}L\text{,}G\text{,}M)$ in which $(p\text{,}l\text{,}g)$ are the BSP parameters for modeling processor component size and interprocessor communication through latency-based and throughput-based cost mechanisms, and $(m\text{,}L\text{,}G\text{,}M)$ are the new parameters that abstract additional memory hierarchies. Each processor component is attached to a memory of size M, and there are also m memory-units accessing a slower memory of unlimited size of latency-based and throughput-based cost $(L\text{,}G)$. A deterministic sorting algorithm is described on this model that is potentially both usable and useful.     

Adjusted quasi-maximum likelihood estimator for mixed regressive,spatial autoregressive model and its small sample bias

Under flexible distributional assumptions, the adjusted quasi-maximum likelihood ($\text{<mi mathsize="small" is="true">ADQML</mi>}$) estimator for mixed regressive, spatial autoregressive model is studied in this paper. The proposed estimation method accommodates the extra uncertainty introduced by the unknown regression coefficients. Moreover, the explicit expressions of theoretical/feasible second-order-bias of the $\text{<mi mathsize="small" is="true">ADQML</mi>}$ estimator are derived and the difference between them is investigated. The feasible second-order-bias corrected $\text{<mi mathsize="small" is="true">ADQML</mi>}$ estimator is then designed accordingly for small sample setting. Extensive simulation studies are conducted under both normal and non-normal situations, showing that the quasi-maximum likelihood ($\text{<mi mathsize="small" is="true">QML</mi>}$) estimator suffers from large bias when the sample size is relatively small in comparison to the number of regression coefficients and such bias can be effectively eliminated by the proposed $\text{<mi mathsize="small" is="true">ADQML</mi>}$ estimation method. The use of the method is then demonstrated in the analysis of the Neighborhood Crimes Data.     

Computing the correct Increment of Induction Pointers with application to loop unrolling

Induction pointers (IPs) are the analogue of induction variables (IVs), namely, pointers that are advanced by a fixed amount every iteration of a loop (e.g., $p=p\to \mathit{next}\to \mathit{next}$). Although IPs have been considered in previous works, there is no algorithm to properly compute the correct amount of pointer jumping (AOPJ) by which IPs should be advanced if loop unrolling is to be applied to loops of the form $\mathit{while}(p)\{\dots p=p\to \mathit{next}\to \mathit{next}\text{;}\}$. The main difficulty in computing the correct AOPJ of IPs is that pointers can be used to modify the data structure that is traversed by the loop (e.g., adding/removing/by-passing elements). Consequently, a simple advancement $p=p\to \mathit{next}$ in a loop does not necessarily mean that $p$ is advanced by one element every iteration. This situation contrasts with the use of IVs, which cannot change the structure of arrays that are traversed by loops. Hence, if $i$ is an IV, $A[i+1]$ will always mean the next element of $A[]$, while if $p=p\to \mathit{next}\text{;}$ is preceded by $p\to \mathit{next}=q\text{;}$ it may be advanced by $k>1$ elements at every iteration. The proposed method for computing the correct AOPJ of IPs and an accompanying loop unrolling technique were implemented in the SUIF compiler for C programs. Our experiments with automatic unrolling of loops with pointers yielded an improvement of 3–5% for a set of SPEC2000 programs. Experiments with a VLIW IA-64 machine also verified the usefulness of this approach for embedded systems.     

Uniform unweighted set cover: The power of non-oblivious local search

We are given $n$ base elements and a finite collection of subsets of them. The size of any subset varies between $p$ to $k$ ($p<k$). In addition, we assume that the input contains all possible subsets of size $p$. Our objective is to find a subcollection of minimum-cardinality which covers all the elements. This problem is known to be NP-hard. We provide two approximation algorithms for it, one for the generic case, and an improved one for the special case of $(p,k)=(2,4)$.The algorithm for the generic case is a greedy one, based on packing phases: at each phase we pick a collection of disjoint subsets covering $i$ new elements, starting from $i=k$ down to $i=p+1$. At a final step we cover the remaining base elements by the subsets of size $p$. We derive the exact performance guarantee of this algorithm for all values of $k$ and $p$, which is less than $H_k$, where $H_k$ is the $k$’th harmonic number. However, the algorithm exhibits the known improvement methods over the greedy one for the unweighted $k$-set cover problem (in which subset sizes are only restricted not to exceed $k$), and hence it serves as a benchmark for our improved algorithm.The improved algorithm for the special case of $(p,k)=(2,4)$ is based on non-oblivious local search: it starts with a feasible cover, and then repeatedly tries to replace sets of size 3 and 4 so as to maximize an objective function which prefers big sets over small ones. For this case, our generic algorithm achieves an asymptotic approximation ratio of $1.5+?$, and the local search algorithm achieves a better ratio, which is bounded by $1.458333\dots +?$.