\section{Structure of Source Files}
\label{sec:FileStructure}
The software bundle contains two packagings of the
new hybrid code (described in the accompanying 
article~\cite{Hanson:2015:RAC})
along with a comprehensive set of test data and a benchmark
code that allows comparison of the efficiency and accuracy
of the new code against other implementations. Makefiles
are also included to assist with building both the test
and benchmark executables.

Wherever possible include files are used so that common
code does not have
to be duplicated to produce single and double precision
versions of the routines.

The following directory structure has been used:

\begin{description}

\item [User Documentation (\filename{Doc/})] 
\mbox{}

  \begin{description}
    \item[\filename{userManual.tex}:] the Latex sources for this user manual; this file includes \filename{BigTab.tex}, \filename{Introduction.tex}, \filename{Testing.tex}, \filename{Benchmark.tex}, \filename{fileStructure.tex}, \filename{Makefile.tex}, \filename{Upate.tex} and \filename{Results.tex},
    \item[\filename{userManual.pdf}:] a pdf version of \filename{userManual.tex},
    \item[\filename{refs.bib}:] the Bibtex data required by \filename{userManual.tex}.
  \end{description}
\item [Algorithm Sources (\filename{Hybrid/})]
\mbox{}

  \begin{description}
  \item[\filename{nrm2HybridMod.f90}:] a Fortran module containing
    single and double precision/real and complex versions of
    both the hybrid routines
    (\fvarn{snrm2}, \fvarn{dnrm2}, \fvarn{scnrm2}, \fvarn{dznrm2})
    and stand-alone
    implementations of the one pass Kahan routines
    (\fvarn{snrm2Kahan}, \fvarn{dnrm2Kahan}, \fvarn{scnrm2Kahan},
     \fvarn{dznrm2Kahan}).

    This also includes a generic definitions for the names
    \fvarn{nrm2} and \fvarn{nrm2Kahan} which call the
    relevant routine depending on the type of the input
    vector.

  \item[\filename{nrm2HybridSubs.f90}:] a file containing the eight
    individual Fortran routines implementing the hybrid and
    one pass Kahan algorithms in single and double precision/real
    and complex.

    This version could easily be incorporated into an
    existing non-module based Fortran library file.

  \item[\filename{onePassRealKahan.inc}, \filename{onePassComplexKahan.inc}:] include
    files containing the common code within the single and
    double precision versions of the one pass version of
    the Kahan real and complex routines. 

  \item[\filename{realHybrid.inc}, \filename{complexHybrid.inc}:] include
    files containing the common code within the single and
    double precision versions of the hybrid real and complex
    routines. Used in \filename{nrm2HybridMod.f90},
    \filename{nrm2HybridSubs.f90},
    \filename{nrm2HybridOrigKMod.f90} and
    \filename{nrm2HybridOrigKSubs.f90}.

  \item[\filename{HybridTail.inc, setStatusFlags.inc}:]
    include files used by hybrid routines to prevent repeating
    sections of code in multiple routines.
    Used in \filename{nrm2HybridMod.f90},
    \filename{nrm2HybridSubs.f90},
    \filename{nrm2HybridOrigKMod.f90} and
    \filename{nrm2HybridOrigKSubs.f90}.

  \item[\filename{nrm2HybridOrigKMod.f90}:] a Fortran module containing
    single and double precision/real and complex versions of
    both the hybrid routines
    (\fvarn{snrm2}, \fvarn{dnrm2}, \fvarn{scnrm2}, \fvarn{dznrm2})
    and stand-alone
    implementations of the original version of the Kahan routines
    (\fvarn{snrm2Kahan}, \fvarn{dnrm2Kahan}, \fvarn{scnrm2Kahan},
     \fvarn{dznrm2Kahan}).

    This also includes a generic definitions for the names
    \fvarn{nrm2} and \fvarn{nrm2Kahan} which call the
    relevant routine depending on the type of the input
    vector.

  \item[\filename{nrm2HybridOrigKSubs.f90}:] 
    a file containing the eight individual Fortran routines
    implementing the hybrid and the original version of the
    Kahan algorithm in single and double precision/real and
    complex.

    This version could easily be incorporated into an
    existing non-module based Fortran library file.

  \item[\filename{realKahan.inc}, \filename{complexKahan.inc}:] include
    files containing the common code within the single
    and double precision versions of the Kahan real and
    complex routines.
    Used in both \filename{nrm2HybridOrigKMod.f90} 
    and \filename{nrm2HybridOrigKSubs.f90}.
  \item[\filename{CInterfaceNrm2.f90}:] interface routines to allow the
    hybrid and Kahan routines to be called from a C
    compiler that is interoperable with the Fortran
    compiler being used.

    \textit{Note:} the method required for building executables
    when using the C interoperability features of Fortran
    may differ from one Fortran/C compiler combination to
    another. This may necessitate changes to the Makefile in
    the \filename{Testing} directory in order to build the test
    program for these routines (\filename{sdTestCInterface}).

    \item[\filename{set\_precision.f90}:] module used by the hybrid and
    Kahan module (as well as alternative \nrm implementations
    and driver programs) to set the kind parameters for single
    (\fvarn{skind}) and double (\fvarn{dkind}) precision. This
    code is portable standard Fortran.


%   \item[\filename{l2\_toms.c}:] C and x87 assembler versions of the
%   \nrm routines. These use 32-bit addressing and
%   are compatible with the Intel C++ compiler.

  \end{description}

\item[Testing Material (\filename{Testing/})]
This directory contains the test module described
in Section~\ref{sec:Testing} of this manual plus
drivers for the new hybrid and Kahan codes, and
all the other BLAS implementations supplied with the package
(described under \filename{OtherVersions} below).

%\mbox{}
  \begin{description}

     \item[\filename{Makefile, runTests}:] makefile and
     bash shell script for building and running the various
     testing executables; see Section~\ref{sec:Makefiles}
     for more details.

     \item[\filename{sdTest.f90}:] This is the common
     main program used to run the full test suite (i.e.,
     single and double precision, real and complex input
     data) on a version of the BLAS Level 1 \fvarn{*nrm2}
     routines. These routines are assumed to be contained
     within a module named \fvarn{nrm2\_other}. The code
     requires the module \fvarn{testSubs} to pass the
     four specific routines (\fvarn{dnrm2}, \fvarn{snrm2},
     \fvarn{dznrm2}, \fvarn{scnrm2}) and the character variable,
     \fvarn{descript}, which is used as a heading in the output
     file to identify the particular set of routines under test.

     For more details on both how to control the scope of the
     testing and how to alter the amount of detail being output 
     see Section~\ref{subsec:testcontrol}.

     Tests~\ref{testW} to~\ref{testY} require that gradual
     underflow is implemented on the platform being used
     to run the tests. The test software calls the function
     \fvarn{ieee\_support\_underflow\_control} to check that
     gradual underflow is supported for single and double
     precision. If this is not the case for either or both
     precisions, a message is output on the standard output
     channel and the tests are skipped.

     \item[\filename{sdTestMod.f90}, \filename{sdTestMod.inc}, 
           \filename{indivTest.inc}:] 
     \filename{sdTestMod.f90} contains two subroutines,
     \fvarn{runDpTests} and \fvarn{runSpTests} which will run
     the single and double precision versions of the test suite
     respectively. These two routines act as wrappers for the
     include file, \filename{sdTestMod.inc}, which actually
     defines all the tests along with expected results and IEEE
     status flags. The include file \filename{indivTest.inc}
     contains routines that run the individual real and complex
     versions of the tests for each precision.

     The use of include files allows much of the same test code to be
     used for each precision.

     \item[\filename{testSubsHybrid.f90},
           \filename{testSubsGen.f90}:] 
     These files all contain a module by the name of \fvarn{testSubs}
     which imports the names as described under
     \filename{sdTest.f90} above. This intermediate module is
     required because we may not have control over either the
     module name containing the BLAS routines or the names
     of the four routines under test. See 
     Section~\ref{sec:Update} for details of how to test a new
     implementation of the \nrm routines.

     \item[\filename{checkTests.f90}:] module used to check test
     results and provide the user with a choice of
     written reports.

     \item[\filename{sdTestBLAS.f90}:] file used to link the
     test suite to either an existing library of BLAS routines
     that will include implementations of the \nrm routines or
     to a file containing just the routines under test (i.e.,
     not contained within a module).

     \item[\filename{sdTestCInterface.c}:] simple driver program
     to test the C interface to the new hybrid routines (in
     \filename{CInterfaceNrm2.f90} within the \filename{Hybrid}
     directory). See also the `Note' under the description of
     \filename{CInterfaceNrm2.f90} above.

     \item[\filename{sdCheckTrue.f90, checkTrueMod.f90,% 
                     indivTestTrue.inc}:] 
     Driver program and equivalent files to
     \filename{sdTestMod.f90} and \filename{indivTest.f90}
     that may be used to check the expected results for each
     of the tests in the test suite that returns a finite
     value against the oracle value.

%    \item[\filename{sdTestScaling.f90, testScaleKahan.f90}:] 
%    THIS NEEDS TO BE COMPLETED


  \end{description}

\item[Benchmark Material (\filename{Benchmarks/})]

This directory contains the Benchmark and supporting software
described in Section~\ref{sec:BenchMark} of this user manual.

  \begin{description}

     \item[\filename{Makefile, runBenchmarks}:] makefile and
     bash shell script for building and running the various
     benchmark executables; see Section~\ref{sec:Makefiles}
     for more details.

     \item[\filename{sdBenchmark.f90}:] driver program that may be
     used to compare the efficiency (execution time)
     and accuracy of the hybrid method against another
     implementation.

     \item[\filename{GenerateTestVectors.f90}:] module
     containing routines that generate test
     vectors in both single and double precision.
     (See Section~\ref{sec:optfile} for details of how to
     generate different types of input data vectors when
     running the benchmark software.)  Generic interfaces are
     used to allow the same calls to be made for both single
     and double data.

     \item[\filename{oracle.f90}:] routines that provide an
     extended precision computation of the $l_2$ norm of a
     vector using a simple square and add loop;
     these are used to compute the errors in the results
     obtained by the various implementations. The multiple
     precision package (Bailey~\cite{Bailey:1995:F9M}),
     provided in the directory \filename{MpPackage}, is
     used to generate the results required the double
     precision data. This is done because not all Fortran
     compilers provide quadruple precision or provide it in
     an inconsistent fashion.

     The oracle module also checks that the value of
     the norm of the data vector being processed by the
     generic routine (\fvarn{VecOracle}) or the two specific
     routines (\fvarn{spVecOracle} -- single precision data
     and \fvarn{dpVecOracle} -- double precision data) is
     representable in the precision being used to define the
     data. If the value is not representable then the module
     variable, \fvarn{normOverflow}, is set to \fvarn{.TRUE.}
     otherwise it is set to \fvarn{.FALSE.}. NOTE: this module
     variable is not used within the current benchmark software.

     The file, \filename{testOracle.f90}, contains a small test
     program that checks the accuracy of the oracle computations
     for a simple vector. It also checks that the oracle routine
     successfully detects that the input data vector would
     cause an overflow if computed in the requested precision.

     \item[\filename{randMod.f90}:] module containing two
     versions of a double precision random number generator
     used to create random test vectors:

     \begin{enumerate}
     \item The two routines \fvarn{dpPortRand} and \fvarn{seed}
     implement the portable random number generator from
     Schrage~\cite{Schrage:1979:MPF}. This was never meant as
     a good quality 64-bit generator but is both efficient and
     portable. The use of the \fvarn{fract} variable should
     ensure that the lower order bits are not all zero, they
     will just not be very random! \fvarn{seed} is used to
     set the initial value of the generator and must be a
     32-bit integer.

     \item The routines, \fvarn{uni64} and \fvarn{fillu},
     implement the generator published by Marsaglia and
     Tsang~\cite{Marsaglia:2004:TUR}.
     This generator is a very good 64-bit generator and is included
     for those users who believe that the quality of the random
     elements may affect the accuracy of the final results!

     Warning: this routine will fail for 32-bit integers if
     the compiler traps integer overflows.
     
     \end{enumerate}

     Also included is the function \textit{randomInt} which
     generates a random integer in the range $[ m, n ]$
     used to set the exponent range of data values.

     \item[\filename{quicksort.f90}:] set of sorting
     routines used to sort input data vectors into
     ascending or descending order. These routines are only
     used if the user options \textit{zeroOneAscending},
     \textit{zeroOneDescending}, \textit{userDefAscending}
     or \textit{userDefDescending} have been chosen for
     \textit{dataDesc} (see Section~\ref{sec:optfile}
     for details).  There is also a generic inteface,
     \textit{qsort}, which allows either single or double
     precision data to be sorted.  A full description of the
     implementation of the quicksort routines that are used
     may be found in~\cite{HandH:2013:MF}.

  \end{description}
 
  \item[Other Existing or Alternative Implementations
  (\filename{OtherVersions/})] 
\mbox{}

  This directory contains other reference implementations of the
  \nrm routines that have been published (either as code or as
  detailed algorithm definitions). Also included are a number
  of variations of these modules which were generated during
  the course of this work to try and improve the performance of
  these original codes. For convenience these sets of routines
  have all been packaged as modules although the original code
  is largely unaltered.
  
  \begin{description}
  
  \item [\filename{BlasOrig.f}:] module containing the
  original Fortran 66 BLAS Level-1 routines as published
  in~\cite{acmalg539}.

  \item [\filename{newOrig.f90}:] the original published code
  restructured to improve readability; this is
  a slightly improved version of the routine that
  appeared in~\cite{Hopkins[1996b]}.  This code uses
  \filename{newOrigComplex.inc} and \filename{newOrigReal.inc}
  to avoid duplication of code in the single and double
  precision versions.

  \item [\filename{newOrigCsum.f90}:] an extension to
  \filename{newOrig.f90} which uses compensated summation to
  improve accuracy when collecting the sums of squares.
  This code uses \filename{newOrigComplexCsum.inc} and
  \filename{newOrigRealCsum.inc} to avoid duplication of code
  in the single and double precision versions.

  \item [\filename{Blue.f90}:] an implementation in Fortran
  90 of Blue's triple accumulator algorithm which was
  presented in Ratfor in~\cite{Blue:1978:PFP}.  The code
  uses \filename{blueComplex.inc} and \filename{blueReal.inc}
  to avoid duplication of code in the single and double
  precision versions.

  \item [\filename{BlueCsum.f90}:] an extension to
  \filename{Blue.f90} which uses compensated summation to
  improve accuracy when collecting the sums of squares.
  This code uses \filename{blueComplexCsum.inc} and
  \filename{blueRealCsum.inc} to avoid duplication of code
  in the single and double precision versions.

  \item [\filename{NewBlue.f90}:] an implementation of Blue's
  algorithm using only two accumulators. A pseudocode version
  of this is provided in~\cite{Hanson:2015:RAC}.  The code
  uses the include files \filename{newBlueComplex.inc} and
  \filename{newBlueReal.inc} to avoid duplication of code in
  the single and double precision versions.

  \item [\filename{lapack.f90}:] the routines included as part of
  the Lapack distribution~\cite{LapackUrl} (\lapackVersion
  and earlier).  The BLAS library routines used by the
  package~\cite{Anderson:1999:LUG} are provided in case no
  platform/compiler specific library is available.

  \item [\filename{lapackCsum.f90}:] an extension of \filename{lapack.f90}
  which uses compensated summation to improve accuracy when
  collecting the sum of squares.

  \item [\filename{lapackCsSc.f90}:] an extension of
  \filename{lapackCsum.f90} which attempts to improve accuracy
  further by using scale factors that are a power of two rather
  than element values in the input vector.

  \item [\filename{origKahan.f90}:] an implementation of the
  original version of Kahan's algorithm alone. A pseudocode
  version of this is presented as Algorithm~5 in~\cite{Hanson:2015:RAC}.
  The code uses the include files \filename{realKahan.inc}
  and \filename{complexKahan.inc} from the \filename{Hybrid}
  directory to avoid code duplication in the single and double
  precision versions.

  \item [\filename{onePassKahan.f90}:] an implementation
  of the one pass version of Kahan's algorithm alone.
  A pseudocode version of this is presented as Algorithm~6
  in~\cite{Hanson:2015:RAC}.  The code uses the
  include files \filename{onePassRealKahan.inc} and
  \filename{onePassRomplexKahan.inc} from the \filename{Hybrid}
  directory to avoid code duplication in the single and double
  precision versions.

  \item[\filename{norm2Intrinsic.f90}:] a set of wrapper routines, \nrm, that
  use the intrinsic function \fvarn{norm2} introduced into the
  2008 Fortran standard~\cite{ISOIEC:2010:ITP}, as a means of
  computing the norm. The wrapper routines are used to provide
  routines of the same name as the original BLAS routines and
  to ensure that special cases are handled consistently.


  \end{description}

\end{description}
