\documentstyle[epsf,fleqn]{article}
\textwidth=4.5in
\textheight=7.2in
\parindent=1em
\newcommand{\eS}{\emptyset}
\newcommand{\ovl}{\overline}
\newcommand{\hsp}{\hspace*}
\newcommand{\vsp}{\vspace*}
\newcommand{\lam}{\lambda}
\newcommand{\ct}{\cite}
\newcommand{\mc}{\multicolumn}
\newcommand{\noi}{\noindent}

\begin{document}

\begin{center}

{\Large \bf A Generic Queuing System for Computationally Intensive Problems}
% How we are solving the Crossing Number Problem}

	\hspace{12pt}

	Bei Yuan, Sean C. Martin, Judith R. Fredrickson,
	Frederick C. Harris, Jr.\\

	Department of Computer Science and Engineering\\
	University of Nevada\\
	Reno, Nevada 89557\\
	\{bei, scmartin, fredrick, fredh\}@cs.unr.edu
	
	\hspace{6pt}
\end{center}

\small
\begin{abstract}
\noindent
	With the availability of inexpensive computer clusters it is
	now economically feasible to attack computationally intensive
	problems using parallel processing.  This paper presents an
	easily adaptable parallel work queue for solving these types
	of problems, many of which lie in the field of graph theory.
	This system allows the user to focus on the problem to be solved
	without having to become an expert in parallel processing details
	(message synchronization, work load balancing, etc.).  Initial
	results are presented for calculating the crossing number of
	complete graphs using this system.

	{\bf Keywords:} parallel, crossing number, complete graph,
	Beowulf cluster
\end{abstract}
\normalsize

\parindent=1em
%\baselineskip=24pt

\section{Introduction}
	\label{sec:introduction}

	\hspace{1em}
	Many combinatorial optimization problems are
	NP-complete. Consequently, computational requirements for
	algorithms are unpredictable and sometimes intense.  Parallel
	computers offer the hope for providing the computational power to
	meet the demands of running these complex algorithms.  However,
	the difficulty in parallelizing most algorithms lies in properly
	and efficiently dividing the work to ensure maximum concurrency
	and simultaneous termination. Work queues have proven to be an
	efficient means of ensuring load balancing, but they often require
	large amounts of message passing as slave processes request work
	from the queue.  These messages make proper synchronization of
	the utmost importance, but they also make it difficult to achieve.
	We attempt to simplify this problem by developing a generic work
	queuing system for medium to large Beowulf clusters, which are
	made of network computers.

	The algorithm Harris and Harris presented in
	\cite{hh96:apafctmcnoag} uses an exhaustive search to find the
	crossing number of a graph.  As graph size increases, exhaustive
	searches can become computationally intensive, taking months or
	even years to complete on a single processor.	   Using a medium
	to large Beowulf cluster and a parallel queuing system that can
	be optimized for problem granularity, we have solved the crossing
	number problem for a complete graph of size less than nine.  However, by
	harnessing the power of large computer clusters and optimizing
	algorithm granularity, this problem may finally be solved for
	larger graphs.	  Our queuing system has been designed to aid in
	solving this, and other, large computationally intensive problems.

	The remainder of this paper is laid out in the following manner:
	Section \ref{sec:background} presents background information
	concerning the crossing number of complete graphs and parallel
	work queues, gives a brief introduction to Beowulf clusters, and
	addresses some of the work that has been done previously. Section
	\ref{sec:genq} describes the proposed implementation of our
	queuing system.  Section \ref{sec:results} describes the solution
	of the crossing number problem using our queuing system and lists
	the results obtained, and Section \ref{sec:concl} finishes the
	paper with our conclusions and future work.

\section{Background and Problem Description}
	\label{sec:background}

  \subsection{The History of the Crossing Number Problem}


	\hspace{1em}
        Determining the crossing number of a graph is an important problem
        with applications in areas such as circuit design and network
        configuration~\cite{leighton83:ciivlsi}.  It is this importance
        that has driven our work in finding the minimum crossing number
        of a graph.

        Informally, the {\it crossing number} of a graph $G$, denoted
        $\nu (G)$, is the minimum number of crossings among all good
        drawings of $G$ in the plane, where a good drawing has the
        following properties:

                %\noindent
                (a) No edge crosses itself,

                %\noindent
                (b) No pair of adjacent edges cross,
                          
                %\noindent
                (c) Two edges cross at most once, and
                                                
                %\noindent                      
                (d) No more than two edges cross at one point.

	\vspace{10pt}

        Although the problem is easily stated and has been well studied,
        not much is known about the general solution.  Erd\"{o}s and
        Guy~\cite{eg:cnog} compiled a survey of what was known in 1973,
        and Tur\'{a}n discussed it {\it via} his brick factory problem
        \cite{turan:1977}.  However, it was not until 1983 that
        Garey and Johnson \cite{gj83:cninpc} proved that finding the
        minimum crossing number of a graph  is an NP-complete problem.
        Because of the difficulty of this problem, the focus of research
        turned away   from finding the minimum crossing number of a
        graph to     sub-problems and other related problems.

        With regard to the sub-problems, there has been work on product
        graphs ranging from the product of $C_{n}$ and graphs of order 
        four~\cite{br80:otcnopocagoof} to                              
        $C_{3} \times C_{n}$~\cite{rb78:tcnoc3xcn},                   
        $C_{4} \times C_{4}$~\cite{dr95:tcnoc4xc4},
        $C_{5} \times C_{5}$~\cite{rt95:iocsatcnoc5xc5},
        and $C_{5} \times C_{n}$~\cite{krs96:tcnoc5xcn}.
        Results have also been published for the bipartite graphs 
        $K_{3,n}$~\cite{rs96:tcnok3nias}, and
        $K_{5,n}$~\cite{kleitman71:tcnok5n}, and the torroidal crossing
        number of $K_{m,n}$\cite{gj69:ttcnokmn} has been found.     
        In 1991 Beinstock \cite{bienstock91:sphcnp}     
        related the crossing number of a graph to the arrangement of
        pseudolines, a topic well studied by combinatorialists.       
                                                                     
        There have also been several related problems that have been
        studied over the years.  These range from the rectilinear crossing
        problem~\cite{oak:otcnocg,GUY72,thomassen88:rdog,th96:apsoaffmormcp}
        to the maximum crossing number of a graph or
        subgraph~\cite{ghprs:citcg,hks73:tgwahcn} to the thrackle
        conjecture~\cite{cottingham:dissertation}.  
	Pach and T\'{o}th       
        \cite{pt:tpocn}                                                
        is a good resource for an overview of references and current
        open problems on crossing numbers for various graph families.
        An interesting discussion of the many different interpretations
        of the term `graph drawing' can be found in \cite{pt:wcniia}.


  \subsection{Parallel Work Queues}

	\hspace{1em}
	Problems such as solving the crossing number of a complete graph
	are computationally intensive and virtually impossible to solve
	using a conventional single processor machine. Fortunately, such
	problems can often be easily broken down into smaller problems.
	The size, or granularity, of these smaller problems can vary
	greatly, but the concept of separate processors tackling portions
	of the overall problem applies regardless of size.

	It is often advantageous to use a divide and conquer strategy when
	dealing with difficult and/or lengthy problems.  These problems
	may have data sets that are completely defined prior to run-time
	and are often divided among the processors, each computing its
	own results from its data set.	This method is referred to as static
	partitioning.  If one processor finishes working it must wait
	idly while the other processors catch up. When a processor is
	idle, the benefits of concurrent execution are not realized in
	their entirety.  In addition, heterogeneous processor clusters may
	make effective partitioning difficult.  Static partitioning
	is effective when data sets are known prior to run-time and the
	execution time of the data can be easily determined. This is
	seldom the case, however.  One solution is dynamic load balancing.

	A work queue is one method of implementing dynamic load
	balancing and thereby ensuring a work load
	that is evenly distributed across many processors or machines
	\cite{qd85:ubspbbbba}.	This load balancing can be either
	centralized, residing with a master process, or decentralized,
	controlled by each slave.  A combination of these two systems
	may also be used.  The work queue is especially useful in load
	balancing with irregular data structures such as an unbalanced
	search tree \cite{Yelick93}.

	In centralized load balancing, the tasks to be performed are held
	by the master and distributed to the slaves as they finish other
	tasks and become idle.	This process minimizes the time each
	slave is idle, thereby maximizing efficiency. One disadvantage
	of centralized load balancing is the possibility of a bottleneck
	while the master distributes tasks.  A bottleneck occurs when many
	slaves request tasks simultaneously, but the master can issue
	only one task at a time. In decentralized load balancing, local
	processors keep their own work pools. This strategy has the benefit
	of avoiding the bottleneck mentioned above.   Decentralized load
	balancing is similar to static partitioning and has the same
	apparent problems.  In more complex systems, the slaves may
	request work from each other or from a centralized master queue.

  \subsection{Cluster Information}

	\hspace{1em}
	Conventional supercomputers or high performance computing systems
	are expensive and beyond the budgets of many researchers. A
	lower cost option available to such research groups is a Beowulf
	cluster, a cluster of high performance workstations designed
	to work in parallel.  Beowulf cluster technology uses clusters
	of commodity machines, relying on standard Ethernet networks
	as a system interconnection, which allows the construction
	of distributed memory parallel computers to serve as a
	``supercomputer''. The normally used network connection is
	100Mb/s Ethernet, although more expensive technology such as
	Myrinet~\cite{bcfksss}	and QsNet~\cite{pcfh} may be used
	as well. These more expensive technologies provide better
	performance because of their low latency, high bandwidth and
	ability to scale well among larger numbers of nodes.

	The typical steps employed in building a Beowulf cluster are as
	follows~\cite{uam}:
	\begin{itemize}
	\itemsep=0pt
	\parskip=0pt
	\item Install an operating system on the front end.
	\item Install each compute node and link them together to form
	a cluster.
	\item Set up a single system view.
	\item Install parallel computing systems. 
	\end{itemize}

	To use a cluster for parallel processing, a software layer
	must be installed to make a virtual parallel machine from a
	group of nodes. In general, this software layer is in charge
	of parallel task creation/deletion, passing data among tasks,
	and synchronizing task execution. Current public tools
	available are PVM, MPI, and BSP.  Cluster computing can address
	a wider range of applications than previously thought for low
	cost~\cite{lr96}.

	Our cluster currently has 128 compute processors.
	60 of these are Pentium III 1 GHz and 68 are Pentium IV
	XEON 2.2 GHz Processors.  Each of these CPUs have 2GB of RAM
	and in total the cluster has more than a half terabyte of disk
	storage.  These compute nodes are connected with Ethernet (for
	NFS) and Myrinet 2000 (for communication), where both MPI and
	PVM techniques are supported.	   We just received funding to
	add 80 more processors.  These processors will be 64 bit
	processors with 2 GB of memory per CPU.

  \subsection{Previous Solutions and Problems}

	\hspace{1em}
	We began with an existing implementation of the sequential
	algorithm to find the crossing number of a complete graph
	given by Harris and Harris in \cite{hh96:apafctmcnoag}.
	This algorithm is a depth first search branch-and-bound
	algorithm which exhaustively covers the entire search
	space. This implementation was parallelized using static
	partitioning by Tadjiev in \cite{tadjiev,th97:pcotmcnoag}.
	As we mentioned earlier, static partitioning does little to
	ensure load balancing. Tadjiev found that it was common in a long
	run for one processor to be working while the others sat idle.
	This idleness can be attributed to an unbalanced tree that was
	statically partitioned across the processors.  An example of
	such a tree is shown in Figure~\ref{fig:unbalanced}.  In this
	example, processors 2 and 3 sit idle while processor 1 works
	toward a solution.

	Tadjiev also showed that very little speedup was noticed in
	solving larger vertex sets when static partitioning was run on
	many processors. By utilizing a generic work queuing system,
	the crossing number problem  and other problems can be solved
	faster and more efficiently with minimal adaptation.

	\begin{figure}[h]
	\epsfxsize=4in
        \centerline{\epsffile{UnbalancedTree.ps}}
	\caption{Unbalanced Search Tree}\label{fig:unbalanced}	
	\end{figure}

\section{The Generic Queuing System}
	\label{sec:genq}
	
	\hspace{1em}
	Many computationally expensive problems have had parallel
	algorithms either proposed or implemented, which makes it easy
	to break problems into jobs (or sub-jobs). Therefore, we decided
	to build a queue of jobs (work) that can be distributed across
	a cluster to harness the parallel computation power available,
	allowing researchers to use it with little, or even no, knowledge
	needed of the parallel programming details.

	A queue is a well-known data structure used to produce first-in,
	first-out behavior for lists of data.  A powerful tool can
	be built by parallelizing the queue data type, allowing the
	first-in, first-out properties to be exhibited across computers.
	A parallel job queue is a specialized form of parallel queue
	that is designed around the processing and distribution of jobs.

	The implementation of the parallel job queue discussed in this
	paper has several key features. One primary goal of the parallel
	job queue is to have a queue that is as generic as possible,
	allowing many types of problems to use the data structure
	without having to reconfigure (or even be knowledgeable about)
	its inner workings.  Another major goal is to hide as much of the
	parallel programming as possible.  In fact, nearly all parallel
	aspects can be hidden.	A secondary goal is that all message
	passing can be performed through the parallel queue interface.

	To keep the queue generic enough to work with many types of
	problems, an abstract data type called package is employed.
	A package is a generic data storage object that holds three
	pieces of information:
	\vspace{-5pt}
	\begin{enumerate}
	\itemsep=0pt
	\parskip=0pt
	\item an identifier telling what type of message is being
		processed,
	\item the number of bytes in the data portion, and
	\item the data portion (represented by raw byte data). 
	\end{enumerate}
	\vspace{-6pt}
	A package is then expected to be sub-classed so that additional
	functionality (such as specific encoding and decoding) can occur.
	For example, a job package is a subclass of package that handles
	the decoding of the raw data into the job format, whatever that
	may be.  For the parallel job queue, a job is a description of
	the data or processing that needs to take place.  Job packages
	can be enqueued on the parallel queue so that other processes can
	retrieve the job package at a later time.  Jobs can be dequeued
	simply by asking for a package from the queue.

	The second goal of hiding the parallel programming was successful
	because we were able to encapsulate all of the general message
	passing into the queue itself and use the message types to
	differentiate job packages from control packages, described in
	the next subsection, virtually all of the parallel programming
	is hidden.  By using a single abstract data type, a package,
	to encode all data transfer, a great amount of flexibility and
	portability is ensured.

  \subsection{Queuing System Implementation}

	\hspace{1em}
	The queuing system was designed to be as generic as possible,
	allowing it to be adapted to a variety of problem sizes and types.
	The system works around jobs.	A job represents whatever amount
	of work can be executed independently.	Thus, the system is easily
	tunable by the user to ensure parallel efficiency.  The size of
	each job, or the amount of work they contain, is referred to as
	the granularity of a task.  Coarse granularity describes a
	task with a large number of sequential instructions that takes
	a significant amount of time to execute \cite{wa:pptaaunwapc}.

	In our proposed implementation, which is illustrated in 
	Figure~\ref{fig:parq}, the master will
	create the first $m$ jobs and place them on the central queue. 
	In general, $m$ is determined by the problem under
	investigation and should be greater than $n$, where $n$ is the number
	of slave processors. The
	master then sends a job to each processor. Each processor will
	create more jobs while processing. These jobs are kept in a local
	work queue by each slave. When a slave's local work queue reaches
	some user-defined limit, it will send the extra jobs to the
	master for placement in the central queue. When a slave is idle,
	it sends a request for a job to the master and, upon receipt,
	begins computation and the filling of its local queue. 
	After initial startup, we have configured the master to hold a certain amount of jobs 
	in the central queue so that
	jobs can be delivered reasonably fast whenever any idle slave
	requests. 
	If a slave
	is idle and the central queue is empty, the idle slave takes a
	job from another slave {\it via} the master. Process termination occurs
	when all slaves are idle and the central queue is empty.

	\begin{figure}
	\vspace{0.3in}
	\epsfxsize=4.5in
        \centerline{\epsffile{workQueue.ps}}
	\vspace{0.1in}
	\caption{Parallel Work Queue}\label{fig:parq}	
	\end{figure}


	We also named signals 
	that the queue will deliver to specified nodes right away
	instead of considering them as a package to be queued.  For
	example, the \verb+STOP+ signal informs the slave to stop
	working. \verb+SLAVE_NEED_JOB+ keeps the master updated on the 
	slave's status, allocating jobs to the slave if necessary. 
	\verb+MASTER_FULL+ helps each slave to know 
	when not to send jobs to the master queue.


	The user is responsible for coding two functions and describing
	the job package.  The first function that must be written is the
	{\tt master\_create\_jobs()} function which creates all of the
	initial jobs and places them in the central queue. The second
	function is the \verb+slave()+ function that is passed a job
	from the queue and is responsible for processing that job and
	possibly creating more jobs to be placed on the local queue.
        A job package is normally a C/C++ data structure that needs to
        be defined and overloaded by the user if it is not represented
        using a built-in data type.

  \subsection{Application with the Crossing Number Problem}
	
	\hspace{1em}
	For the crossing number problem, the job is simply an integer
	array filled in with its graph description (such as its current
	crossings, region list, edges needs to be added to make it
	complete, etc.).  The layout of our job is illustrated in
	Figure~\ref{fig:mcnjob}.  
	The {\tt Array Size} is the number of integers in the array.
	The {\tt Current Crossings} the number of crossings that this job
	currently has.	The {\tt Graph Size} is the number of vertices
	other than crossings.  The {\tt Edge List} is a list of edges
	to be added to the rest of the graph represented by this array.
	The {\tt Region List} is a list of regions that  represent the
	embedding of the current graph.


	\begin{figure}[h]
	\epsfxsize=4.5in
        \centerline{\epsffile{jobArray.ps}}
	\caption{Job Data for the Crossing Number Problem}
	\label{fig:mcnjob}	
	\end{figure}

	The \verb+master_create_jobs()+ function is quite simple.
	It reads data in from a file and places those jobs into the
	initial queue.	We designed it this way so that we could easily
	modify the process to solve different sub-problems that will
	arise in our future work.  The \verb+slave()+ function will
	receive a job, decode the integer array, modify the data using
	the algorithm presented in \cite{hh96:apafctmcnoag}, and encode
	it to a new integer array as a new job.

	The last thing we had to define were special signals.  In solving
	the crossing number problem we only needed one new signal,
	\verb+MCN_UPDATE+.  This signal broadcasts a better minimum
	crossing number that a slave has found to all of the other
	slaves. This signal allows every slave to throw away those jobs
	that were in the queue that have more crossings then the current
	best solution.

\section{Results}
	\label{sec:results}

	\hspace{1em}
	The time needed to process one job varies depending on the 
	definition of the job. The algorithm we use to calculate minimum
	crossings of complete graphs breaks the problem down into very
	small parts. Hence, a job is composed of only a couple thousand
	integers, which requires a trivial amount of time to process.

	In Tables \ref{tab:k86slaves} and \ref{tab:k88slaves}, the 
	second column is the number of
	jobs that each slave handled. The next three columns are the number
	of jobs sent from the master to the slave or the slave to the master.
	The master only sends jobs to the slaves when they request jobs.
	The slaves send jobs to the master when the slave's queue is full
	or when the master requests jobs so an idle slave can 
	continue working.

	\begin{table}[bth]
	\vspace{0.2in}

	\begin{tabular}{|c|r|r|r|r|}\hline
	& \# jobs & \# jobs master & 
	\multicolumn{2}{c|}{\# jobs to master} \\

	& processed & sent to slave & 
	slave full & 
	master requests \\ \hline
	Slave1 	&  8,342,722 & 1,514,960 &   500,512 & 394,885 \\
	Slave 2	&  9,798,531 & 1,276,270 & 1,200,044 & 122,004 \\
	Slave 3 &  5,663,196 &   890,280 & 1,195,091 & 316,733 \\
	Slave 4 &  5,280,137 &   517,435 & 1,043,396 & 116,819 \\
	Slave 5 &  5,997,357 &   942,616 &   375,144 & 114,378 \\
	Slave 6 & 11,615,911 & 1,942,186 & 1,601,353 & 103,384 \\ \hline
	Total  & 46,697,854 & 7,083,747 & & \\ \hline
	\end{tabular}

	%Total time taken: 12,517 seconds
	Total time taken: $\approx 3.5$ hours

	\caption{$K_{8}$  Run with 6 Slaves}
	\label{tab:k86slaves}
	\end{table}

	\begin{table}[bth]
	\begin{tabular}{|c|r|r|r|r|}\hline
	& \# jobs & \# jobs master & 
	\multicolumn{2}{c|}{\# jobs to master} \\

	& processed & sent to slave & 
	slave full & 
	master requests \\ \hline
	Slave 1 & 5,860,119 & 1,066,788 & 124,171 & 168,214 \\
	Slave 2 & 5,852,334 &   672,011 & 106,191 & 205,251 \\
	Slave 3 & 6,252,721 &   500,014 & 352,193 & 1,066,193 \\
	Slave 4 & 5,918,188 &   618,149 & 509,321 & 452,096 \\
	Slave 5 & 5,437,214 &   925,381 & 157,449 & 168,598 \\
	Slave 6 & 5,207,427 &   897,845 & 856,689 & 164,729 \\
	Slave 7 & 5,652,174 & 1,096,038 & 837,283 & 152,531 \\
	Slave 8 & 6,219,062 &   353,452 & 391,920 & 335,845 \\ \hline
	Total  & 46,399,239 & 6,129,678 &         &  \\ \hline
	\end{tabular}

	%Total time taken: 8,493 seconds
	Total time taken: $\approx 2.4$ hours
	
	\caption{$K_{8}$  Run with 8 Slaves}
	\label{tab:k88slaves}
	\end{table}

	Table~\ref{tab:k86slaves} shows the data for $K_{8}$ run with 6
	slaves, and Table~\ref{tab:k88slaves} shows the same problem with
	8 slaves.  Figure~\ref{fig:jobsprocessed} shows the same problem
	run with a variety of processing slaves.  This figure shows
	that the more nodes used, the more evenly the jobs are distributed
	among the slaves.  The queue can manage a large numbers of jobs
	(up to several million) and signals while maintaining a balanced
	load. We also found several features that we did not expect.

	\begin{figure}
	\epsfxsize=4.5in
        \centerline{\epsffile{jobProcessed.ps}}
	\caption{Jobs Processed by Each Slave for $K_{8}$}
	\label{fig:jobsprocessed}
	\end{figure} 

	\begin{enumerate}
	\item There is a trade-off between the number of slaves to be
	used and the number of jobs to be processed. The total number of jobs
	handled by all the slaves is different even if they deal
	with the same vertex set. Since the processes run in parallel,
	the time required to generate the first best solution is roughly
	the same. Therefore, the more nodes we use, the bigger the
	total amount of jobs created.

	\item A good maximum queue size selection makes a
	difference. Generally speaking, the machine will complete jobs
	faster when there are not many jobs piled in the queue taking up
	system resources. Each slave will send extra jobs from its local
	queue whenever the maximum size is reached. Most of the time,
	we tend to increase the number of nodes in order to expedite the
	processing speed.  As a consequence, there will be a huge number
	of jobs passed back to the master from slaves.	We need to be
	cautious when choosing the number of nodes to be used so that
	the number of jobs that slaves send back will not be beyond the
	master machines capacity. When we ran $K_{8}$, we set the maximum
	size of slave queues to 1 million jobs, and the master queue
	size to 2
	million. This works well for 5 to 16 processors. We also tested
	smaller and larger queue sizes and believe that this range is
	a good general configuration.

	\item Currently the master sends one job at a time. 
	We are unable to show whether it is more practical to send
	multiple jobs because the speed of dealing with one job varies
	as time goes by. For the crossing number problem, the time to
	complete a job decreases as better solutions are generated. If
	the master sends multiple jobs to slaves, the slaves will be
	kept busy and less communication time will be spent as slaves
	ask for fewer jobs.  However, sending multiple jobs may result
	in a slightly unbalanced load prompting requests for more work
	from some slaves.

	\end{enumerate}

\section{Conclusions and Future Work}
	\label{sec:concl}

	\hspace{1em}
	In this paper we have documented our creation of a generic
	queuing system for computationally intensive problems.  
	By developing a standard queuing system for use in Beowulf
	clusters, we have opened the door for easy adaptation of existing
	algorithms to solve a wide variety of problems.  Using our
	system, costly development can be avoided.  The system allows for
	easy tuning for optimum performance based on the computational
	intensity or job granularity of the chosen algorithm.

	We have explained how this system works and have demonstrated its
	usefulness by presenting results from the crossing number problem.
	These results have laid the foundation for what we envision as
	a fruitful path of research. 

	We plan to use this queuing system to solve the crossing
	number problem for larger graphs.  Harris and Thorpe showed in
	\cite{th96:apsoaffmormcp} that the actual rectilinear 
	crossing number diverges from the currently accepted value given
	by Guy in \cite{eg:cnog}.  This result leads us to believe
	that the non-rectilinear conjectured formula is also not a
	tight bound.  Using our queuing system as a framework to achieve
	load balancing, the non-rectilinear problem may be solved for
	$K_{11}$ or greater. We also plan to use the queuing system to
	find the crossing number of a bipartite graph. Very little adaptation
	should be necessary to use our queuing system for this and other
	similar graph theory problems.

	In future versions, we want to make the system
	even more general by looking at the possibility of slaves
	being able to query other slaves and being allowed to transfer
	jobs directly from each other, without the use of the master
	as an intermediary. We plan to make queue size variables
	user definable at run-time rather than only at compile time.
	This will possibly be implemented to include a graphical user
	interface developed using an open source, readily available
	library such as GTK.

	%Our results have led us to question
	%whether a stack implementation will work better
	%than a queue
	%for problems
	%using depth first search.


\quad

%\baselineskip 13pt
\itemsep=0pt
\bibliographystyle{plain}
\bibliography{/staff/fredh/papers/bibdir/xing,/staff/fredh/papers/bibdir/fredh,/staff/fredh/papers/bibdir/thesis,/staff/fredh/papers/bibdir/parallel,bib}
\end{document}

