International Journal of High Speed Computing

Partitioning a set of objects into homogeneous clusters is a fundamental operation in data mining. The k-means-type algorithm is best suited for implementing this operation because of its efficiency in clustering large numerical and categorical data sets. An efficient parallel k-means-type algorithm for clustering data sets on a distributed share-nothing parallel system is considered. It has a simple communication scheme which performs only one round of information exchange in every iteration. We show that the speedup of our algorithm is asymptotically linear when the number of objects is sufficiently large. We implement the parallel k-means-type algorithm on an IBM SP2 parallel machine. The performance studies show that the algorithm has nice parallelism in experiments.

One major source of overhead for conventional network communication is the involvement of operating system to allow for virtual sharing of the network interface card among applications and its processing of the UDP/TCP/IP headers on behalf of applications. The involvement of operating system results in overheads such as extra write/read operations to the kernel buffer through which each inbound/outbound messages should pass. Another overhead comes from scheduling which may hinder immdiate sending or receiving of messages to and from network interface buffer. Recently, U-Net over Fast Ethernet [9] addressed this problem and proposed a new scheme which circumvents the operating system in processing the network communication. However, since the approach has removed IP header and provides multiplexing in the ethernet layer, it is only applicable to an ethernet LAN. In this paper, we define a new protocol by which messages are allowed to move across routers and the virtual sharing of network interface card is supported with minimal overhead. In a word, we extended the U-Net over Fast Ethernet [9] beyond routers to WAN and hence opening a new way to exploit vast amount of computing resources all over Internet. With our protocol, cluster computing over any part of WAN is realizable as far as total delay caused by intervening routers is tolerable to the application. As a justification of our approach, we show a small part of WAN containing a router exhibits latency comparable to (differ by less than 1 ms) that of a shared ethernet. Another motivation for our approach is the observation that the aggregate bandwidth of two subnets (part of WAN) is greater than that of a single subnet (LAN). With same number of hosts, each connection will experience more available bandwidth with the part of WAN than the LAN. The experiment over WAN involving a router shows reduction of latency comparable to that of U-Net over Fast Ethernet.

Several existing studies have revealed that pipelined circuit switching (or PCS for short) can provide superior performance characteristics over wormhole switching. This paper proposes a new analytical model for PCS in high-radix high-dimensional k-ary n-cubes augmented with virtual channel support. The model uses Random Walk Theory to analyse the backtracking actions of the message header during the path set-up phase, and M/G/1 queueing systems to compute the mean waiting time that a message experiences at a source node before entering the network. Results from simulation experiments confirm that the proposed model exhibits a good degree of accuracy for various network sizes and under different operating conditions.