Applying Functional Programming Theory to the Design of Workflow Engines

Abstract
Declaration
Acknowledgements
Related publications
1 Introduction
	1.1 Case study: Image similarity search
	1.2 Language requirements
	1.3 Programming models for workflows
	1.4 Functional programming
	1.5 Thesis overview
	1.6 Thesis outline
2 Background and Related Work
	2.1 Independent tasks
	2.2 Fixed task structure
	2.3 Workflows
		2.3.1 Types of workflows
		2.3.2 Aims of scientific workflow languages
		2.3.3 Programming models
		2.3.4 Orchestration and choreography
		2.3.5 Error handling
		2.3.6 Execution management and monitoring
		2.3.7 Languages and systems
		2.3.8 Limitations
	2.4 Parallel functional programming
		2.4.1 Modes of evaluation
		2.4.2 Parallelism and efficiency
		2.4.3 Expressing parallelism
		2.4.4 Laziness and parallelism
		2.4.5 Graph reduction
		2.4.6 Input/Output
		2.4.7 Relationships between functional programming and workflows
		2.4.8 Discussion
	2.5 Web services
		2.5.1 Concepts
		2.5.2 Service oriented architecture
		2.5.3 Standards
		2.5.4 Language support
		2.5.5 Asynchronous RPC
		2.5.6 State
		2.5.7 REST
		2.5.8 Applicability to workflows
	2.6 XQuery
		2.6.1 Existing approaches to web services integration
	2.7 Summary
3 Workflow Model
	3.1 Overview of our approach
	3.2 Workflow language concepts
	3.3 Challenges addressed
		3.3.1 Expressiveness
		3.3.2 Control flow constructs
		3.3.3 Abstraction mechanisms
		3.3.4 Data manipulation
		3.3.5 Implicit parallelism
		3.3.6 Service access
		3.3.7 Distributed execution
	3.4 Orchestration and choreography
		3.4.1 Orchestration
		3.4.2 Choreography
	3.5 Extended lambda calculus
		3.5.1 Lambda calculus
		3.5.2 ELC
		3.5.3 Built-in functions
		3.5.4 Syntax
		3.5.5 Programming example
		3.5.6 Evaluation modes
		3.5.7 Parallelism
		3.5.8 Network access
	3.6 ELC as a workflow language
		3.6.1 Tasks
		3.6.2 Conditional branching and iteration
		3.6.3 Embedded scripting languages
		3.6.4 Representation
		3.6.5 Abstract workflows
	3.7 Example workflow: Image similarity search
		3.7.1 Workflow implementation
		3.7.2 Task implementation
	3.8 Support for higher-level languages
	3.9 Summary
4 The NReduce Virtual Machine
	4.1 Goals
	4.2 Execution environment
		4.2.1 Frames
		4.2.2 Abstract machine
		4.2.3 Data types and graph representation
		4.2.4 Pointers and numeric values
	4.3 Parallelism
		4.3.1 Automatic detection vs. manual specification
		4.3.2 Sparking
	4.4 Frame management
		4.4.1 Blocking and context switches
	4.5 Networking
		4.5.1 Abstracting state manipulation
		4.5.2 The I/O thread
		4.5.3 Asynchronous call example
	4.6 List representation
		4.6.1 Array cells
		4.6.2 Array references
		4.6.3 Sharing
		4.6.4 Converting between representations
		4.6.5 High-level list operations
	4.7 Distributed execution
		4.7.1 Architecture
		4.7.2 Message passing
		4.7.3 Distributed heap management
		4.7.4 Work distribution
		4.7.5 Frame migration
	4.8 Summary
5 XQuery and Web Services
	5.1 Benefits of XQuery as a workflow language
	5.2 Language overview
		5.2.1 Data types
		5.2.2 Expressions and control flow constructs
		5.2.3 Path expressions
		5.2.4 Element constructors
		5.2.5 Example
		5.2.6 Relationship to other languages
	5.3 Web service support
		5.3.1 The import service statement
		5.3.2 Mapping function calls to SOAP requests
		5.3.3 Stub functions
		5.3.4 Parallelism
	5.4 Usage examples
		5.4.1 Collating content from multiple sources
		5.4.2 Processing of data structures returned from services
		5.4.3 Two-dimensional parameter sweep with graphical plotting
	5.5 Implementation details
		5.5.1 Runtime library
		5.5.2 Data representation
		5.5.3 Static context
		5.5.4 Dynamic context
		5.5.5 Tree construction
		5.5.6 Compilation process
	5.6 Discussion
		5.6.1 Factors that made implementation easy
		5.6.2 Factors that made implementation difficult
		5.6.3 Performance implications
		5.6.4 Advantages over existing RPC mechanisms
		5.6.5 Advantages over existing workflow languages
	5.7 Summary
6 Managing Parallelism
	6.1 Evaluation modes and detection of parallelism
		6.1.1 Advantages of lazy evaluation
		6.1.2 Advantages of strict evaluation
		6.1.3 Detecting parallelism
		6.1.4 Comparing parallelism in both cases
		6.1.5 Laziness and service requests
		6.1.6 Summary
	6.2 Limiting request concurrency
		6.2.1 Available capacity
		6.2.2 TCP connection establishment
		6.2.3 Determining when a connection has been accepted
		6.2.4 Client-side connection management
	6.3 Spark pool management
		6.3.1 Costs of sparking
		6.3.2 Minimising direct costs
	6.4 Load balancing of requests during choreography
		6.4.1 Processing assigned sparks
		6.4.2 Determining when a machine is idle
		6.4.3 Deciding which sparks to run
		6.4.4 Postponing connections
		6.4.5 Spark addition and activation
		6.4.6 Example
		6.4.7 How many frames to distribute?
	6.5 Limits on connection rates
	6.6 Summary
7 Performance Evaluation
	7.1 Experimental setup
	7.2 Service invocation
		7.2.1 Number of tasks and task throughput
		7.2.2 Granularity
	7.3 Types of parallelism
		7.3.1 Data parallelism
		7.3.2 Nested data parallelism
		7.3.3 Divide and conquer
		7.3.4 Physical pipelining
		7.3.5 Logical pipelining
		7.3.6 Multi-stage data parallelism
		7.3.7 Summary
	7.4 Data transfer
		7.4.1 Divide and conquer
		7.4.2 Physical pipelining
		7.4.3 Logical pipelining
		7.4.4 Multi-stage data parallelism
		7.4.5 Discussion
	7.5 XQuery-based workflows
		7.5.1 Speedup and data transfer vs. number of nodes
		7.5.2 Speedup vs. granularity
		7.5.3 Data transfer vs. number of tests
		7.5.4 Impact of code size
	7.6 Internal computation
		7.6.1 ELC
		7.6.2 XQuery
	7.7 Summary
8 Summary and Conclusions
	8.1 Summary
	8.2 Review of case study: Image similarity search
	8.3 Contributions
	8.4 Future work
		8.4.1 Compiler optimisations
		8.4.2 XQuery
		8.4.3 Fault tolerance
	8.5 Conclusions
A Lambda Calculus and Graph Reduction
	A.1 Reduction order
	A.2 Additional functionality
	A.3 Extensions
	A.4 Graph reduction
	A.5 Parallel evaluation
B XQuery Compilation
	B.1 Overview
	B.2 Format of compilation rules
	B.3 Initial compilation stages
	B.4 Code generation
	B.5 Final compilation stages