Patent ID: 8099733
Filing Date: 2012-01-17
Classification: G06F,G16B,Y10S

Abstract:
1. In a parallel data processing architecture for search, storage and retrieval of data of a database responsive to queries for specific data of said database, said parallel data processing architecture comprising a) a plurality of host processors comprising at least one root host processor responsive to a client query for said specific data of said database and at least one other host processor; b) a communication system coupling said plurality of host processors, said plurality of host processors being capable of communicating with one another; and c) host processor memory, a method of balancing workload between said plurality of host processors comprising: each of said plurality of host processors maintaining load information of processor capacity and search queue length of said host processor, each of said plurality of host processors further maintaining information of a search queue of client queries at said host processor for said specific data of said database; each of said plurality of host processors broadcasting said load information of its processor capacity and search queue length to at least one other of said plurality of host processors; and each of said plurality of host processors bringing its search queue of client queries into balance with another of said plurality of host processors according to a time constant responsive to receipt of said broadcast capacity and load information, said balancing including exchanging unprocessed search requests with a recipient host processor responsive to a stochastic selection process to determine the recipient host processor of an exchanged search request between said root host processor and said recipient host processor thereby minimizing a time required to respond to client queries for retrieval of responsive data from said database, said bringing into balance comprising exchanging a block of search requests from host processors having long average waiting times to host processors having short waiting times and adjusting a size of a block of exchanged requests according to relative processing speeds of host processors and inter-processor communications protocol between the host processors.