Sapan Bhatia
email: sapan.bhatia@inria.fr

Charles Consel
email: charles.consel@inria.fr

Julia Lawall

Memory-manager/Scheduler Co-design: Optimizing Event-driven Servers to Improve Cache Behavior

Event-driven programming has emerged as a standard to implement high-performance servers due to its flexibility and low OS overhead. Still, memory access remains a bottleneck. Generic optimization techniques yield only small improvements in the memory access behavior of event-driven servers, as such techniques do not exploit their specific structure and behavior.

This paper presents an optimization framework dedicated to event-driven servers, based on a strategy to eliminate data-cache misses. We propose a novel memory manager combined with a tailored scheduling strategy to restrict the working data set of the program to a memory region mapped directly into the data cache. Our approach exploits the flexible scheduling and deterministic execution of event-driven servers.

We have applied our framework to industry-standard web servers including TUX and thttpd, as well as to the Squid proxy server and the Cactus QoS framework. Testing TUX and thttpd using a standard HTTP benchmark tool shows that our optimizations applied to the TUX web server reduce L2 data cache misses under heavy load by up to 75% and increase the throughput of the server by up to 38%.

Introduction

High-performance network applications have exceptional scalability requirements, as they need to keep pace with ever-increasing network speeds and user demands. For this reason, they have been studied as a separate class of applications and have been optimized extensively [START_REF] Begel | BPF+: Exploiting global data-flow optimization in a generalized packet filter architecture[END_REF][START_REF] Clark | An analysis of TCP processing overhead[END_REF][START_REF] Engler | DPF: Fast, flexible message demultiplexing using dynamic code generation[END_REF][START_REF] Mccanne | The BSD packet filter: A new architecture for user-level packet capture[END_REF][START_REF] Pai | Flash: An efficient and portable web server[END_REF][START_REF] Van Renesse | Masking the overhead of protocol layering[END_REF][START_REF] Welsh | SEDA: An architecture for wellconditioned, scalable internet services[END_REF]. One optimization that has proved very successful in providing high efficiency in the face of heavy loads is the use of the event-driven paradigm [START_REF] Banga | Better operating system features for faster network servers[END_REF][START_REF] Pai | Flash: An efficient and portable web server[END_REF]. Indeed, the commercially-available servers that are recorded to deliver the highest performance [START_REF]The SPECWeb99 Benchmark[END_REF], such as TUX [START_REF] Lever | An analysis of the TUX web server[END_REF], Flash [START_REF] Pai | Flash: An efficient and portable web server[END_REF] and Zeus [START_REF]Zeus web server[END_REF] for the HTTP protocol and SER [START_REF]Sip express router[END_REF] for telephony, are event-driven.

The event-driven paradigm implements the processing of a task as a finite state machine, in which the transitions between machine states are triggered by events. This paradigm generalizes naturally to concurrent tasks, by implementing each task as a continuation that records its own data and machine state. As compared to process and thread-based programs that rely on the OS for scheduling, [copyright notice will appear here] an event-based program performs its own task management, permitting the use of specialized data structures and scheduling strategies. Furthermore, in the event-driven paradigm, the concurrency between tasks is controlled, as tasks can only be interrupted at event handler boundaries, making it easy to reason about the code within an event handler, as compared to the case of process and threadbased programs, where switching between tasks can occur at any point. Finally, as compared to general event-driven programs such as GUIs, event-driven servers have a highly deterministic execution, in which one event handler typically sets up the next. This property makes it possible to reason about task behavior across a sequence of events.

Today, the conditions affecting the performance of servers are rapidly changing. Network speeds are increasing and main memory is becoming large enough to replace disks as the principal storage unit for server data. Accordingly, network transfer and disk I/O have become less of a performance bottleneck, exposing other overheads as the dominating factor in server performance. The most prominent of these overheads is that of memory accesses. Indeed, memory latency exceeds that of computations by up to two orders of magnitude. Heavy loads on the server cause an explosion in the working data set of a server, reducing the effectiveness of the data cache and thus causing a sharp degradation in performance. Generic compiler optimizations have proved ineffectual in significantly improving this memory access behavior. Nevertheless, we observe that the specific properties of event-driven network servers introduce several optimization opportunities.

This paper presents an optimization approach based on the codesign of a memory manager with a scheduler. In effect, this codesign introduces cache-awareness into the scheduling algorithm. We exploit the determinism of event-driven servers to allow the memory allocator to be able to statically predict memory requirements across a sequence of events. We exploit the fact that an eventdriven server manages its own task scheduling to augment the provided scheduling algorithm to take cache behavior into account. Our approach is the most effective on programs for which the runtime footprint of a single task is guaranteed to be smaller than the L2 cache size, as is the case in many high-performance network servers. In this case, we take measures to prevent the working data set of the program from overflowing this cache.

Our optimizations are integrated into a server program through static analysis and transformation of its implementation. We provide tools that automatically carry out these operations in an event-driven C program that conforms to a memory allocation and scheduling interface specified in this work. Legacy event-driven programs can be modified to expose this interface using specific code annotations or by implementing stub functions corresponding to those in our interface. The integration process then consists of four steps. First, static analysis is used to identify the server's memory-usage behavior. Second, a customized memory allocator is generated according to the size distributions and lifetimes of the data, identified in the first step. Third, invocations of the original memory allocator in the program are replaced by invocations of the customized one. Finally, the scheduler is modified to use feedback from the customized allocator to ensure that the total data set stays in a cache-aligned, cache-sized region.

The contributions of this paper are as follows:

• We present a novel cache-aware memory allocator, called the "Stingy Allocator". This allocator can be used with any program for which the size distribution of data objects is either defined statically or can be predicted by profiling. In coordination with specific scheduling refinements, the Stingy Allocator can be used to nearly eliminate cache misses from an event-driven server.

• We present a strategy to extend the scheduler of an eventdriven program to incorporate an additional cache criterion. This strategy is enabled by the Stingy Allocator.

• We describe a set of program analysis tools that apply the approach to existing programs.

• We present an evaluation of our work in the context of the following event-driven servers: The TUX, thttpd and Flash web servers, the Squid proxy server and the Cactus QoS framework. Specifically, we evaluate two aspects of our work: (i) The applicability of our static analysis tools and (ii) The impact of our optimizations on program throughput. For the latter, experiments conducted on TUX and thttpd show that our optimizations reduce the number of L2-cache misses by up to 75% and increase server throughput on the network by up to 38%.

The rest of the paper is organized as follows. In Section 2 we describe the architecture of event-driven programs from the point of view of caching behavior. In Section 3 we propose a novel memory allocator, the Stingy Allocator, and a scheduling strategy to prevent the working set of an event-driven program from overflowing the data cache. Section 4 describes our toolkit for applying our optimization approach. Section 5 evaluates our approach on a number of event-driven servers. Finally, Section 6 presents related work and Section 7 concludes.

Event-driven Servers

Event-driven servers have a rigidly defined structure, making them amenable to specific optimizations. This section gives an overview of event-driven servers, emphasizing their characteristic structure. It also discusses their cache behavior, bringing out specific caching inefficiencies and their impact on the server's performance.

Overview

An event-driven program typically consists of a single thread that loops continuously, processing a stream of events. Events may be generated on the occurrence of some I/O, or issued explicitly by the program itself. Once intercepted, an event is interpreted, and the tasks corresponding to it are considered for scheduling. Scheduling a task amounts to executing the handler associated with the event in the task's current context. Once initiated, a handler runs uninterruptedly until completion. 1Concurrency is managed in an event-driven program by representing each task as a continuation consisting of the current task state and a pointer to the code to be executed in response to the next event. This representation constitutes one of the biggest differences between thread and process-based servers and event-driven servers. While thread and process-based servers abstract task state as OSlevel threads or processes, event-driven servers store this state in concise application-specific data structures, and are free to use and manipulate them as required.

Event-driven servers are distinguished from other event-driven servers such as GUIs by their highly deterministic behavior. Typically, an event-driven server receives a fixed sequence of events in the processing of a given request. For example, a HTTP server first receives a request, then parses it, then processes it, etc. Accordingly, we can view the structure of an event-driven server as a series of stages, as illustrated in Figure 1.

Overall, the implementation of an event-driven server can be characterized by the following elements:

• Stages: A stage is represented by a function and is bound to one or more events. It has a small number of possible predecessor and successor stages. A stage may allocate data for local use, and may allocate or use data that persists over multiple stages. Before terminating, a stage queues zero or more successor stages to be executed next.

• Tasks: A task represents the complete processing of a request. As such, it defines an execution context for the server. This execution context includes data that is shared by multiple stages of the task execution.

• Events: An event triggers the activation of a stage in a task context. Events may be external and generated by I/O operations or internal and generated by the program.

• Scheduler: The scheduler is the part of the server implementation that iteratively extracts stages waiting to be executed and executes them in their corresponding task contexts. It is typically implemented by a designated function.

Performance of Event-driven Servers

When the amount of data manipulated by a server is more than the size of the main memory, its throughput is limited by I/O activity such as disk reads. The behavior of servers under such circumstances has been widely studied [START_REF] Pai | Flash: An efficient and portable web server[END_REF][START_REF] Elmeleegy | Lazy asynchronous i/o for event-driven servers[END_REF]. When the amount of memory available is sufficient to maintain this data, as is more often the case today, I/O is no longer a bottleneck. Then, the efficiency of the server implementation plays a crucial role in the performance of the server. Two aspects of the server implementation dominate its resulting performance: its interaction with the OS and its behavior with respect to the underlying hardware caches. The event-driven architecture has been shown to be highly successful in optimizing the OS-interaction aspect of servers [START_REF] Banga | Better operating system features for faster network servers[END_REF] by eliminating the need to use threads and processes to abstract tasks altogether, and facilitating the use of efficient OS primitives for non-blocking operations. Once the bottlenecks associated with the scalability of OS primitives have been removed, the overheads associated with memory accesses become more important and can be observed to cause a significant degradation in server performance.

In the following subsection, we will study the cache behavior of event-driven servers on a highly efficient implementation of the event-driven architecture, namely, the TUX web server. Through the TUX web server, we will study the influence of the data cache on server performance.

Caching behavior

At any given time, the memory that is used by an event-driven server consists of the data that is (i) live in the contexts of the various concurrent tasks, (ii) the global state of the server, and (iii) the local data of the currently executing stage. When the total size of this data exceeds the capacity of the cache, cache misses occur, resulting in expensive main-memory accesses. The capacity of the cache depends on both its size and its associativity, i.e., how many cache lines are available to represent a given memory location.

We illustrate the cache behavior of an event-driven server using the program shown in Figure 2(a). This program consists of five stages, each annotated with the objects live in the stage. For objects that are dynamically allocated, the beginning of its lifetime is marked by an explicit memory allocation and the end by an explicit deallocation. For statically allocated objects, the lifetime can be seen as the time between the first and last use of the object. In this program, we assume that all objects are the same size, and that the scheduling is round-robin.

We consider the concurrent execution of four tasks, whose processing begins simultaneously, as illustrated in Figure 2(b). Each task allocates an O2 object in its first stage. As this object is also used by stages 2 and 3, it becomes part of the context of each task. Thus, at the end of the processing of the first stage the memory requirement of the server consists of four instances of O2. Since the total size of these instances is much smaller than the size of the cache, the data can be expected to fit within it. The second and third stages allocate and then use the additional object O1. Thus, between the second and third stages, the memory requirement of the server consists of four instances of O2 as well as four instances of O1. This requirement exceeds the cache capacity. In this case, the state of the server can no longer be maintained in the cache and must be spilled into memory, requiring expensive memory accesses.

When a server is heavily loaded, memory traffic is high, and cache behavior can degrade quickly. On a cache miss, an arbitrary data item is evicted. If this item is live, which it is likely to be when the server is under heavy load, it will soon be reloaded, probably evicting another live data item, leading to a domino effect. This degradation in performance can be observed in practice. Figure 3(a) shows the change in the L2 data-cache misses when running TUX as a function of the concurrency of the workload (i.e., the number of concurrent requests in flight over the network).

The performance regime in Figure 3(b) consists of three regions. In the leftmost region (marked 'I'), throughput increases constantly as the latency of packets over the network gives the server enough time to process the small batches of requests sent. Thus, increasing the number of concurrent requests uses up an increasingly large fraction of this available latency. When the concurrency increases to an extent that fully utilizes this latency, then the server begins to process multiple requests concurrently (region 'II'). We believe that the improvement in this region comes as a result of improved instruction locality. The decreasing number of i-cache misses in Figure 3(a) support this belief. In the third region (region 'III'), we find that the amount of data corresponding to the requests treated concurrently no longer fits in the L2 cache. Thus, there is a steady increase in the number of L2-cache misses along with a steady degradation in performance. Finally, in the fourth region, the server is overwhelmed with requests and spends the majority of the CPU cycles available to it in dealing with new requests. As a result, its throughput drops abruptly, and it fails.

Eliminating Data-Cache Misses

Our goal is to eliminate cache misses in the largest cache present on the system, i.e., an external cache (e-cache), or L2 cache in the absence of an e-cache. We find this overhead to be the biggest bottleneck, and penalties arising due to L1 cache misses less significant. Indeed, on most modern processors, the difference between memory latency and L2 (or e-cache) latency is more than two orders of magnitude greater than the corresponding difference between L2 and L1 cache latencies.

The working data set of an event-driven server comprises a stack, assumed to be allocated statically, global data, which may be allocated dynamically or statically, and per-task state, which is all data that is maintained within a stage or across multiple stages. The per-task state typically makes up the bulk of an event-driven server's working set, and is thus the main target of our optimization strategy.

In this section, we give an overview of our optimization strategy in three parts. First, we briefly describe the three main data regions that constitute the program working set. Second, we give an overview of our cache-aware memory allocator, the Stingy Allocator. Finally, we discuss the role of the scheduler in cache utilization, focusing on adjustments in the scheduler to improve cache behavior.

The Stingy Allocator

The Stingy Allocator is the basis of our optimization strategy to improve the cache behavior of a program. It controls where and how much memory is allocated to ensure that the data items in the working data set of a program will not cause collisions in the L2 cache. The control over where memory is allocated is obtained by allocating memory from a memory region that is mapped directly to the L2 cache 2 The control over how much memory is allocated is obtained by first analyzing the program to determine its memory requirements and then laying out this required memory in the cache-mapped region such that there are no cache collisions. All the components of the server's working data set are contained in this memory region. Furthermore, each object is assigned an area The Stingy Allocator manages a fixed number of each kind of object, and guarantees that as long as a program uses only these objects, they will not interfere with one another in the cache. The Stingy Allocator must thus be configured by selecting the number of each kind of object. This selection takes into account constraints on the size of the cache, the set of objects used within a given stage, the sequence in which the object used by a given are allocated, and the desirability of concurrency at the various stages.

The maximum memory usage that a single stage can entail is the case where one task is executing in the stage and all of the others are waiting to enter the stage. In this case, we must ensure that all of the objects live in these tasks fit within the cache. For each stage, we thus obtain the following constraint, where L is the set of objects live at the beginning of the stage, A is the set of objects allocated during the stage, size(Oi) is the size of object Oi, nO i is the number of instances of object Oi managed by the Stingy Allocator, and τ is the amount of cache space allocated to per-task state:

ΣO l ∈L(size(Ol ) • nO l ) + ΣO a∈A size(Oa) ≤ τ For example, in the case of stage 2 in Figure 2(a), we obtain the following constraint:

size(O2) • nO 2 + size(O1) ≤ τ
We obtain further constraints from the allocation order of objects that are live in the same stages. Consider objects O2 and O1 in Figure 2(a), which are both live in stages 2 and 3. As the object O2 is allocated before the object O1, any task that is holding an O1 object must be holding an O2 object as well. Thus:

nO 2 ≥ nO 1
More generally, the relation between any two objects can be characterized in terms of the standard compiler dominance relation between their allocation and deallocation sites. That is, for any objects Oi and Oj , if the allocation site of Oi dominates that of Oj and the allocation site of Oj dominates the deallocation site of Oi, then we obtain the constraint:

nO i ≥ nO j
The above constraints generally leave substantial latitude in the numbers of the various objects. As the number of objects managed by the Stingy Allocator determines the number of tasks that can be executing at a given stage, it is desirable to solve the constraints with respect to an objective function that maximizes the number of objects available for stages where high concurrency is beneficial, e.g. to improve the i-cache behavior. A detailed discussion of how to encode concurrency strategies in the objective function is out of the scope of this paper. However, for the sake of clarity, we take up an example.

Let us consider a simple model of an event-driven program's use of the instruction cache. We define a run of a stage as a series of consecutive executions of it for a batch of tasks. We assume that the first iteration of a run causes instructions of the stage to be fetched from the main memory so that the following iterations retrieve these instructions from the cache. Then, the cost of the first iteration of a stage is significantly greater than that of the second and subsequent iterations. Let the cost of the first iteration be defined for each individual stage i, by the quantity wi.

We define the instruction-fetch work done in processing N tasks as the sum of the cost of processing the first iteration of every run involved in treating the tasks. Thus, minimizing the amount of instruction-fetch work done also minimizes the number of instruction cache misses.

If Mw is the instruction-fetch work function, S is the set of stages and Ls is the set of objects live in stage s, then Mw is defined as follows:

Mw(N ) = Σs∈S ws • N minO l ∈Ls nO l
The intuition behind taking the minimum of the number of the objects that are live in a stage is the fact that the flow of tasks through a stage is limited by the minimum number of objects of a given kind available at the stage.

By combining the constraints dictated by the data-cache with this objective function, we obtain an Integer Programming minimization problem. Thus, the configuration of the Stingy Allocator, i.e., the number of objects of each kind, is obtained by solving this problem.

Scheduling for cache efficiency

The Stingy allocator never allocates an object that would cause it to exceed its configured bounds. To avoid the complexity and inefficiency of starting to execute a stage only to have its memory allocation fail, we augment the server's scheduler to make it aware of the memory requirements of each stage and the current ability of the Stingy Allocator to satisfy these requirements. This information is provided by a table that maps a stage to the set of objects that are allocated by the stage and the number of those objects currently available. As an example, consider one possible solution for the number of objects O1 and O2 in Figure 2(a), nO1 = 3, nO2 = 4. In this case, when the scheduler is about to schedule task 4 at stage 2, it will discover that the Stingy Allocator does not have any more instances of object O2 left to allocate, and will thus select a task that is in another stage. In addition to the benefit of ensuring that an elected task can run its current stage to completion, this approach allows the scheduler to group homogeneous tasks into batches and check the availability of memory for an entire batch at a time.

Integrating the Stingy Allocator with legacy code

Our optimization framework consists of a set of analysis and transformation tools that are used to convert a program to use the Stingy Allocator and the associated scheduling strategy. In this section, we first describe the use of these tools by a programmer who wants to optimize an event-driven server, and then present the analyses and transformations underlying the tools.

A programmer's eye view

We take as a starting point an event-driven server written in C. Our framework requires that the server conform to a fixed interface, describing the signatures of relevant functions such as queuing a stage and allocating memory. If the program conforms to a compatible interface, as is mostly the case for TUX, Flash and Squid, source-code annotations can be used to identify the corresponding functions. If not, wrapper functions need to be introduced. Figure 4 contains examples of the annotations and wrappers used in TUX. The add tux atom function is identified as the interface construct QueueStage. Its first argument is labeled with "T", indicating that it represents the task context, and the second with "S", indicating that it represents the stage to be queued. Similarly, the functions tux malloc and tux free are identified as the Malloc and Free constructs respectively. The tux malloc req function, used to allocate a request data structure, cannot be labeled directly as it does not accept any argument corresponding to the size of the allocated data. This function must hence be wrapped in a new function that accepts as argument the object size. Invocations of tux malloc req in the source code must then be textually replaced by invocations of tux malloc req wrap.

Once the server has been made to conform to our interface, it can be analyzed and transformed by our tools. This process entails the following steps:

Analyzing memory utilization. The first step is to analyze the memory utilization of the program. For this purpose, we provide the tool memwalk, which analyzes the program and provides conservative approximations of three quantities: (i) The amount of stack used by the program (ii) The amount of per-task state allocated and deallocated categorized for the various objects. (iii) The amount of global state used by the program. The output of this tool is used in the subsequent steps.

Parameterizing the Stingy Allocator. The second step is to generate a configuration of the Stingy Allocator that corresponds to the output of memwalk. This output is fed into a tool named stingygen that yields a memory map. This memory map is to be compiled with the server implementation and is referenced by the Stingy Allocator, which is linked in as a library.

Using the allocator. The third step is to transform the program to use the Stingy Allocator in place of the original memory allocator used by the program. This step involves simply replacing the occurrences of Malloc in the stages, by invocations of the Stingy Allocator memory allocation function StingyAlloc. StingyAlloc differs from Malloc in that its argument is an index indicating the allocation site rather than the requested memory size.

Modifying the scheduler. The final step is to modify the scheduler. In this step, the programmer modifies the scheduler to incorporate the cache criterion. Figure 6 shows a round-robin scheduler for an event-driven program, before and after being modified to include this criterion. Apart from the usual scheduling criteria summarized by the function Elect And Dequeue Task, an invocation to the StingyDynCheck function, defined by the Stingy Allocator library, checks whether enough instances of all the objects required to schedule a task are available.

The modification of the scheduler is the only step for which we do not provide an automatic tool, because the scheduling code may vary widely. In our experience with a variety of legacy event-driven servers (see Section 5), it is easy for the programmer to identify the code implementing the scheduling criteria and to augment this code with the appropriate use of StingyDynCheck.

Analyses and transformations

We now describe the analyses and transformations implemented in the memwalk and stingify tools.

Identifying the stages and the scheduler

To analyze the stack, global, and per-task state of a program, memwalk needs to identify the stages and to distinguish the code implementing these stages from the implementation of the scheduler. We begin with the identification of the stages. We represent the program stages using a graph called the Stage Call Graph (SCG). Nodes in the SCG represent functions, and edges represent either a call relationship (function A calls function B) or a queuing relationship (function A queues function B to be scheduled). Call relationships are referred to as as call edges, and queuing relationships as event edges. Call edges are indicated by C language function calls. Event edges are indicated by analyzing invocations of the construct Queue Stage, described in Figure 5. Thus, if a function A invokes Queue Stage(atask, B) then an event edge is added between the nodes corresponding to A and B. In either case, the destination of the edge may be represented by a function pointer. Thus, our implementation provides an alias analysis that enumerates all the aliases of the function value.

Once the SCG has been built, the stages are the call-edge connected components that are reachable from at least one event edge. Sometimes, an edge has both incoming call edges and incoming event edges. We treat such cases by duplicating the corresponding node in the graph, so that the call-edge pointed copy becomes part of a larger stage, and the event-edge-pointed copy becomes the entry point of another stage. Sometimes, the constructed SCG can consist of many connected components, corresponding to independent functionalities of the server (such as implementations of different protocols). Some of these functionalities may include undesired ones that pollute the SCG. For example, the Squid proxy server uses its event interfaces for interacting with users, application timeouts etc.. As such functionalities are likely not subject to heavy loads, they need not be optimized using the Stingy Allocator. The exploration of an SCG may be started at a particular node specified as input to the memwalk tool.

The entry point of the scheduler is the function implementing the Schedule item of the interface. The analysis identifies as the scheduler all of the functions reachable by a depth-first traversal from the node representing this function up to the entry points of the stages A part of the SCG obtained by analyzing the TUX Web server is summarized in Figure 7. To save space, we have collapsed functions belonging to a particular stage into a node representing that stage. Each node in this modified SCG is annotated with the total number of functions that constitute the corresponding stage, along with its estimated stack utilization, as calculated by the analysis in the following section.

Memory Analysis

The second analysis carried out by memwalk is the analysis of memory used by the stages. We will describe this separately for each type of state.

Analysis of per-task state

The analysis of per-task state can be seen as an analogue of the liveness analysis performed by an optimizing compiler. An object is live between the time that it is allocated and the time that it is deallocated. Each stage is associated with a transfer function that updates the set of live objects. When an object is allocated using the Malloc construct, it is added to the live set, and when one is deallocated using the Free construct, it is removed from the live set. At the end of the analysis, those objects that are live at terminal stages are assumed global. The remaining objects belong to per-task state.

The liveness of objects also determines object dependencies. If two objects are live in the same stage, then they are dependent and may not share memory (in much the same way as program variables that are live together may not share the same registers). Such objects are assigned to different memory regions by the Stingy Allocator. Objects that cannot be allocated simultaneously for a task may be assigned the same region. To maximize memory utilization, the dependency analysis colors a graph with objects at the nodes and edges specifying a dependency between objects. The number of colors is minimized to maximize the utilization of the cache. Each color is ultimately allocated a separate region by the Stingy Allocator.

Cycles in the SCG are identified by enumerating stronglyconnected components using Tarjan's algorithm [START_REF] Tarjan | Depth-first search and linear graph algorithms[END_REF]. For objects allocated in such cycles, the number of instances that may be allocated per task is unbounded. Thus, by default, these objects are not managed by the Stingy Allocator and continue to use the original memory allocator. Alternatively, such data can be managed by the Stingy Allocator if the programmer annotates the code with an estimate of the number of instances of each such object that may be allocated per task. The occurrence of cycles in the SCG usually corresponds to situations in which a stage queues itself to be executed in the future due to the unavailability of input data, or a temporary failure. For example, the parse request stage in 7 queues itself when the input buffer received by it is incomplete, and hence cannot be parsed in the current iteration. In most such situations, objects that are live in the stage are usually allocated in the first iteration and preserved over subsequent ones. Indeed, loops in the SCG in which every iteration performs an allocation are rare.

Analysis of global state

Global state is identified during the analysis of per-task state, as described above. Once an object has been classified as global, it is sub-classified based on its size. Objects smaller than a user-defined threshold are labeled final and those that are larger are labeled temporary. Final objects are kept permanently in the cache, while temporary objects are stored in uncached memory and copied in on demand. 3 The threshold used for the classification typically depends on the object size distribution and the size of the cache. Keeping too many or too large objects in the cache permanently can leave insufficient room for per-task state, reducing the number of tasks that can be treated concurrently.

Stack analysis

The total stack space required is calculated to be the sum of the maximum stack used by the scheduler before scheduling a task, added to the maximum stack used by the stages. The amount of stack required for a function is computed as the sum of two quantities: (i) The amount of memory consumed by all the local variables and (ii) The stack required to call the function, which includes the sizes of the arguments, the return address and saved registers. The amount of stack required along a path is calculated by summing the stack requirement for each function along the path. Recursion is handled in the same way as cycles in the SCG, by identifying strongly-connected components in the call graph.

If the stack usage varies widely, then allocating the maximum amount required may result in many locations in the cache-aligned region that are very rarely used. Indeed, exceeding the cache region allocated to the stack does not result in a program crash due to a stack overflow, but causes the stack to spill out of the Stingy Allocator's cache-aligned region resulting in cache misses. Although this situation is undesirable, it does not prevent the program from functioning correctly. Thus, the memwalk tool not only calculates the maximum size of the stack, but also summarizes the sizes around which the stack utilization of various paths is clustered. The programmer may edit this information before passing it to stingygen, to choose a smaller stack size if desired.

Parameterizing the Stingy Allocator

Using the memory utilization information provided by memwalk, the tool stingygen generates a configuration for the Stingy Allocator, which includes a memory map and some data structures used for accounting. The memory map is based on an analysis of the sizes of different state components. For the stack and final global state, a fixed amount of space is set aside permanently, while for the per-task state, dependencies between objects as discussed in Section 3 are used to distribute objects into different regions. The sizes of the individual regions depend on the calculated values of the per-object limits, as calculated in Section 3.

Code Annotations

The Stingy Allocator relies on determinism in the memory utilization behavior of the program. However, in the presence of features such as recursion and dynamically sized buffers, statically determining the memory utilization is not possible. To enable the optimization of programs in the presence of these features, we propose the use of specific annotations in the source code. These annotations are currently provided as C language attributes. These annotations have already been mentioned in Section 4.1.

Figure 8 illustrates such an annotation in the source code of a server, and a sugare version of the output generated by the stingify tool. The new attributes we introduce, stingy size and stingy count can be used to provide an optimistic estimate of the size of a dynamically sized object, or that of the maximum number of per-task instances of an object in the case of dynamic loops, recursion and SCG cycles. The code generated for the allocation of the object contains a guard to check if the specified size of the object is exceeded, and accordingly uses the default allocator or the Stingy Allocator. No such guard is required in the corresponding deallocation of the object, as objects allocated by the Stingy Allocator can be identified on the basis of their virtual memory addresses.

The estimates passed to the tools may be intuitive, or obtained by profiling. As an example of the former, TUX contains a cycle in its SCG at the request parsing stage. This loop ensures that parsing begins only when a request has been fully received. Although the analysis reports that the request buffer allocated in this stage has potentially unbounded instances, examining the code reveals that this buffer is only allocated on the first iteration. Thus, an annotation is added to set its stingy count attribute to 1. Although generating these estimates is error-prone, the use of a guard guarantees that a misestimate does not corrupt the functioning of the program. At worst, providing a wrong estimate reduces performance.

Experimental evaluation

We have applied our tools to five event-driven programs: The TUX, thttpd and Flash web servers, a test server using the Cactus QoS framework and the Squid proxy server. In the first part of this section, we discuss the applicability of our approach by giving an overview of the effort involved in processing these programs. All these programs, with the exception of Flash, are available publicly. The Cactus QoS framework is distributed as a library along with the implementation of an example transport protocol (CTP). We applied our tools to a test server that uses this protocol.

To evaluate the performance benefits of our approach, we evaluated the performance of unmodified versions of TUX and thttpd on a real network using a standard benchmarking tool for HTTP servers [START_REF]Apache HTTP server project[END_REF], and then did the same for a version optimized using our toolkit. In Section 5.2 we present an analysis of these experiments.

Applicability

We have claimed that the interface used by our tools for the purpose of analysis and transformation is general and widely applicable. In this section, we support this claim with evidence in the form of actual code excerpts, shown in Figure 10, containing some representative wrappers and annotations written to apply our toolkit to the programs considered.

In Cactus, a stage specifies the next event to be executed using the function cRaiseEvent. This function is used by the current stage to specify the next event to be scheduled for the current task. Since a function annotated with QueueStage needs to accept a pointer to a stage function, cRaiseEvent is wrapped in a function that accepts an additional argument of a pointer to a function. The field, lBinding->p in the event data structure contains the function pointer that the event is bound to. As mentioned in Section 4, an alias analysis collapses this function pointer into a set of candidate successor stages. This stage is passed as an additional parameter to the function.

In thttpd, the scheduler looks up the stage to be executed in a particular context using a connection state, represented by an enumerated type. Thus, queuing the next stage to be scheduled amounts to modifying the value of the connection state. This functionality is thus wrapped in a new function, which accepts the additional parameter of the function corresponding to the stage to be executed, along the lines of the previous example.

Collapsed SCGs corresponding to Flash, the Squid server and thttpd are shown in Figure 9. Other SCGs are left out to save space.

Evaluation

We ran our experiments on a Gigabit network between a powerful client system with two Intel Xeon processors running at 3GHz, and a server system with an Intel Pentium III M running at 1.4GHz. The server has 1Mb of L2 cache and 2GB of RAM. The aim of using a powerful machine as the client is to ensure that operation is bottlenecked on the server. We verified that this was the case using Cactus:

extern int cRaiseEvent( cevent *pev, ceventmode em, int nDelay, int nUrgency, int cDynamicArgs); extern int cRaiseEvent_wrap( cevent *pev, funcptr_t *func_pointer, ceventmode em, int nDelay, int nUrgency, int cDynamicArgs) __attribute__ ((QueueStage ("X","S","X","X","X","X"))); extern int cRaiseEvent_wrap ( void SetSelectHandler(int fd, SelectHandler s, int forRW) __attribute__ ((QueueStage ("X", "S", "X")));

Squid:

void eventAdd(const char *name, EVH * func, void *arg, double when, int weight) __attribute__ ((QueueStage ("X","S","X","X","X"))); void commSetSelect(int fd, unsigned int type, PF * handler, void *client_data, time_t timeout) __attribute__ ((QueueStage ("X","X","S","X","X"))); the Netperf benchmark suite [START_REF]Netperf: A network performance benchmark[END_REF]. We used the Apachebench [START_REF]Apache HTTP server project[END_REF] package to measure performance. Apachebench has been previously used to evaluate HTTP server performance in the systems community [START_REF] Von Behren | Capriccio: scalable threads for internet services[END_REF][START_REF] Welsh | SEDA: An architecture for wellconditioned, scalable internet services[END_REF]. Figures 11(a) and 12(a) show the variation of requests serviced per second with increasing concurrency in the two servers. For the most intense loads, the requests serviced by TUX increase by about 38% and L2 cache misses decrease by about 75%. For thttpd, the throughput increases by about 12% and the number of L2 cache misses by about 53%.

We attribute the massive difference between the improvements observed in the two servers to the difference in their original implementations. TUX is highly optimized and makes use of low-level OS interfaces to achieve the highest possible efficiency [START_REF] Lever | An analysis of the TUX web server[END_REF]. On the contrary, thttpd is an ordinary http server that uses standard OS mechanisms and is not known as a high performance server. As one may observe in Figures 11(a) and 12(a), the absolute through- Comparison of the performance of the original thttpd server to that of the optimized thttpd server put of TUX is about 2.5 times that of thttpd. We consider that TUX is representative of the target applications of our work because it is already highly optimized, making the cache bottleneck all the more significant.

The cache misses that remain even after the inclusion of the Stingy Allocator occur due to interference with modules on which the servers depend that are not modified to use the Stingy Allocator. Such modules include OS modules such as the protocol stack and the file system drivers and external library functions. In order to entirely eliminate data-cache misses, one would need to include these modules in the optimization process through explicit OS support for the Stingy Allocator. We are currently in the process of exploring this extension.

Related Work

With the increasing gap between microprocessor speeds and memory access times, the optimization of cache usage has been an intensively researched topic in the compiler and systems community. Due to its sheer size, it is impossible to cover the full body of work in the domain. We will focus on the works that are the most related to ours.

Larus and Parkes presented Cohort scheduling [START_REF] Larus | Using cohort scheduling to enhance server performance[END_REF], which is another scheduling strategy to improve the cache performance of concurrent programs. Cohort scheduling induces consecutive runs of stages by accumulating (cohorting) tasks at specific stages. This policy is configured by heuristics based on inter-stage delays and queue lengths, and has the most positive impact on static global state and the instruction cache. Our work strikes a balance between per-task state and global state by using static analysis. Better instruction-cache locality was also the goal of Blackwell [START_REF] Blackwell | Speeding up protocols for small messages[END_REF], in his work on optimizing TCP/IP stacks. He showed that by processing several packets in a loop at every layer, one could induce better reuse of the corresponding instructions.

Cache-conscious data placement has been used to optimize the caching behavior of generic programs [START_REF] Calder | Cache-conscious data placement[END_REF][START_REF] Chilimbi | Cache-conscious structure definition[END_REF][START_REF] Chilimbi | Cache-conscious structure layout[END_REF]. These works use program analysis and profiling information to efficiently arrange objects in memory, and fields within objects. While the goal of these efforts is to reduce the number of cache misses in generic programs, our work focuses on the specific problem of reducing data cache misses in concurrent programs. Specifically, although such data placement can be beneficial for a certain number of object instances, it does not address the situation in which the number of these instances is multiplied as a result of increasing concurrency.

Rajagopalan et al. have considered the problem of improving the performance of event-driven programs in general [START_REF] Rajagopalan | Profile-directed optimization of event-based programs[END_REF]. As this class of programs includes programs such as GUIs that depend heavily on user interaction and are thus highly non-deterministic, their approach relies on dynamic profiling to identify commonly occurring event-handler sequences rather than the static analysis used in our approach. This reliance on dynamic profiling implies that they can only optimize synchronous events, as it is only in this case that there is guaranteed to be a connection between two event handlers that occur in sequence. In contrast, our approach is independent of whether events are synchronous or asynchronous. The kinds of optimizations performed are also quite different, as they consider primarily optimizations in the call-and-return interface between event handlers such as function inlining, whereas we consider cache behavior. These optimizations are orthogonal, and applying both kinds of optimizations to servers that raise many synchronous events could yield further speedups.

Finally, the last body of related work optimizes concurrent programs (both event-driven and thread-based) through intelligent resource management. SEDA [START_REF] Welsh | SEDA: An architecture for wellconditioned, scalable internet services[END_REF] and Capriccio [START_REF] Von Behren | Capriccio: scalable threads for internet services[END_REF] use resource monitors to implement resource-aware scheduling. These monitors are installed in various stages, and periodically sample the level of utilization of CPU, memory and file descriptors. The scheduler uses the values of resource consumption at these monitors to favor the scheduling of stages that free resources. Although this policy improves overall performance by de-prioritizing resource bottlenecks, it does not expressly go to improve caching behavior.

Conclusion and Future Work

We have presented an optimization framework to remove the dominant bottleneck of memory accesses from event-driven servers. Our framework includes a novel memory allocator that compacts the program's working set in a fixed region of memory, restricting it to the L2 cache, and a scheduling strategy that coordinates with the allocator to ensure that the scheduling of tasks in the server respects these constraints. A set of program analysis tools has been implemented to apply our optimizations.

We have applied our approach to the five test programs to evaluate the applicability of our work. Benchmarking the TUX and thttpd web servers has shown that data-cache misses are reduced by up to 75%, and the overall throughput of the server increases by up to 38%.

As future work, we would like to explore techniques to scale event-driven servers to multiprocessors [START_REF] Zeldovich | Multiprocessor support for event-driven programs[END_REF] in the context of our optimizations. We are also working on a system to encode specific concurrency strategies as objective functions when configuring the Stingy allocator. Finally, we are working on a framework to integrate the Stingy allocator into thread and process-based servers.

Figure 1 .

 1 Figure 1. An event-driven server.

Figure 3 .

 3 Figure 3. Throughput degradation with increasing L2 cache misses.

  (a) Per-task state (b) Cache overflow

Figure 2 .

 2 Figure 2. Per-task state during program execution

Figure 4 .

 4 Figure 4. Example annotations and wrappers for TUX.

Figure 7 .

 7 Figure 7. A fragment of the Stage Call Graph (SCG) of TUX. nf denotes the number of functions in a stage, and sc its maximum stack utilization in bytes. Functions belonging to the same stage have been collapsed into a node representing the stage.

Figure 8 .

 8 Figure 8. Guiding the tools using code annotations.

Figure 10 .

 10 Figure 10. Excerpts of Code Annotations for the Programs. The test programs are annotated and instrumented with wrappers to expose a standard interface for the purpose of analysis.

  Figures 11(b) and 12(b) show the corresponding variation in L2 cache misses.

Figure 9 .Figure 11 .Figure 12 .

 91112 Figure 9. Portions of collapsed SCGs for the test programs (Call-edges have been deleted.)

Various strategies such as event-coloring[START_REF] Zeldovich | Multiprocessor support for event-driven programs[END_REF] and per-stage thread pools[START_REF] Welsh | SEDA: An architecture for wellconditioned, scalable internet services[END_REF] have been explored as a means to scale event-driven programs to multiprocessors. We are currently in the process of exploring the extension of our work in these directions. In its current form, we assume a uniprocessor system.

In our implementation for the Pentium II and Pentium III processors, aligning the memory region with the cache amounts to reserving and using a physically contiguous range of memory of the size of the L2 cache. The Linux 2.6 kernel provides a set of interfaces to obtain virtual memory ranges that are contiguous in physical memory.

2006/2/23

2006/2/23

http_post_header [nf=1,sc=20] http_send_body [nf=7,sc=72] http_process_message [nf=45,sc=234] http_dirlist_head [nf=6,sc=72] list_directory [nf=2,sc=642] do_dir_line [nf=3,sc=1140] http_dirlist_tail [nf=9,sc=80] do_send_abuf [nf=71,sc=56] flush_request [nf=1,sc=0] http_lookup_vhost [nf=6,sc=413] parse_request [nf=47,sc=846]

2006/2/23

An explanation of the implementation of this aspect of the Stingy Allocator is omitted for brevity.

2006/2/23

2006/2/23

Queue Stage : S × T → void A function that queues a task to be executed at a particular stage. Scheduler : void → void

The implementation of the scheduler.

Malloc : int → O

A function to allocate a block of memory for an object in O. Free : O → void A function that frees the memory allocated for an object in O.

Where,

is the set of tasks. O is the set of objects used by various stages in the course of processing tasks. Each allocation site corresponds to a distinct object. while


Malal Kane

Benyebka Bou-Said

Comparison of Homogenization and Direct Techniques for the Treatment of Roughness in Incompressible Lubrication

Homogenization is a formal mathematical two-scale averaging process that can be ap-plied to roughness problems and can replace previous heuristic averaging procedures, which have sometimes led to ambiguous results. This procedure was previously math-ematically developed and applied to compressible flow problems. The purpose of this paper is the development of a special form of Reynolds equation for such homogenized conditions applied to the incompressible Newtonian case. The equation allows the calcu-lation of the operating characteristics of a contact by taking into account the local geometry of surfaces while making a substantial improvement in computing time. The method allows for the study of rough surfaces, but requires considerably fewer calculated points than for traditional deterministic discretization methods.

Introduction

An understanding of the influence of roughness on the surface of machine elements during lubrication can contribute to an improvement of the performance of the device and an increase in the lifespan of the mechanism. In turn, proper prediction of the performance of a lubricated contact depends on a rigorous characterization of the involved surfaces and on a sufficiently accurate representation of the lubricant flow behavior. When the operating conditions are severe, i.e., the fluid films are very thin, the effect of roughness is all the more significant.

As is well known, the development of the theory of lubrication for thin films first appeared in 1886 with the mathematical model established by Reynolds. The governing equation, which can be written in various forms, is a second-order elliptic partial differential equation for the pressure, with the surface film shape entering as part of known variable coefficients. The Reynolds equation does not usually admit to analytical solutions, and the complexity of surfaces due to roughness is one of many complications that require numerical approaches. In this study, our contribution is to set up a new model that takes into account the surface roughness phenomena by using a new technique of calculation known as homogenization, which will be explained shortly. Taking into account the roughness of surfaces in the study of lubrication can be done considering the statistical parameters of roughness. There are a number of papers in the literature that could be characterized as using stochastic analysis ͓1-14͔͑ considering some sort of averaged surface properties͒, and another group that uses deterministic analysis of a specific surface description ͓15-20͔. For our concerns, we introduce a third methodology called homogenized analysis ͓21-23͔, which amounts to dividing the problem into two parts: a local problem ͑i.e., the roughness͒ and a homogenized problem for the global properties. This approach will be discussed to illustrate its advantages as well as its disadvantages compared to the others.

Homogenization Analysis

The approach of homogenization amounts to rewriting the problem as two others: a local problem and a homogenized prob-lem. The coefficients of the homogenized problem depend on the solution of the local problem. The difficulty of this technique lies in the decoupling of the two problems, starting from the homogenized problem because of the presence of nonlinearities. The coefficients of the homogenized problem can be calculated only after treatment of the former.

In 2000, this technique was developed and was applied to the compressible Reynolds equation by Buscaglia and Jaı ¨͓21͔.Itwas further revealed that this method is well adapted to the problems with an anisotropic roughness ͓22,23͔. It is also a technique that does not require a very fine grid account for the effect of roughness. Roughness is taken into account during the calculation of the local problem, where less computing time is required compared to deterministic techniques. To see the advantages of this approach, Fig. 1 is shown, based on the compressible flow analysis of Jaı änd Bou-Saı ¨͓23͔. From this figure we can observe that the stochastic analysis does not capture the directional aspect of the roughness ͑i.e., the pressure is symmetric about the midplane͒. As for the deterministic analysis, it accurately portrays the pressure shape, but requires a very high number of discretization points to do so. On the other hand, the results obtained from homogenized analysis accurately capture the shape and magnitude of the pressure field but with considerably less numerical effort.

In Sec. 3, this technique will be applied to a Newtonian incompressible flow analysis to obtain the homogenized Reynolds equation.

Homogenized Reynolds Equation

We begin with the incompressible Reynolds equation

ٌ͑h 3 ٌp ͒ϭ⌳ ץh ץx 1 (1)
where p(x,y) is the pressure, h(x,y) the film thickness, the viscosity is , sliding occurs only in the x direction at speed V, and ⌳ϭ6V. The coordinates of the Cartesian reference system are xϭx 1 , yϭx 2 , zϭx 3 , and the domain is ⍀ϭ(x 1 ,x 2 ) ͑see Fig. 2͒. We introduce the concept of local coordinates by writing

h͑x 1 ,x 2 ͒ϭh 0 ͑ x 1 ,x 2 ͒ϩ␦ ͩ x 1 , x 2 ͪ (2)
1

The symbol h 0 denotes the global film thickness, and ␦ is the roughness contribution. The latter is a periodic function of period ϭ1/n r , where n r is the ''roughness number'' or the number of roughness cycles across the contact ͑in an order-of-magnitude sense͒.

Let us introduce the concept of local variables setting ( 1 , 2 ) ϭ(x 1 /,x 2 /) and make an asymptotic development of the pressure by writing

p͑x 1 ,x 2 ͒ϭ p 0 ͑ x 1 ,x 2 ͒ϩ p 1 ͑ x 1 ,x 2 , 1 , 2 ͒ϩ 2 p 2 ͑ x 1 ,x 2 , 1 , 2 ͒ ϩ¯(3)
where p 1 ,p 2 , . . . are periodic functions of the variables ( 1 , 2 ). We use the following rule of differentiation

ץ ץx i ϭ ץ ץx i ϩ 1 ץ ץ i (4)
and substitute Eq. ͑3͒ into Eq. ͑1͒. We then gather terms of power of and obtain the following equations for powers 0 , 1 , and 2 , respectively:

ץ

ץx 1 ͫ h 3 ͩ ץp 0 ץx 1 ϩ ץp 1 ץ 1 ͪͬ ϩ ץ ץx 2 ͫ h 3 ͩ ץp 0 ץx 2 ϩ ץp 1 ץ 2 ͪͬ ϭ⌳ ץh ץx 1 Ϫٌ .͑h 3 ٌ x p 1 ͒ (5) ٌ •͑h 3 ٌ p 1 ͒ϭ⌳ ץh ץ 1 Ϫٌ h 3 .ٌ x p 0 (6) ٌ x •͑h 3 ٌ x p 1 ͒ϭ0 (7)
with ٌ x and ٌ , respectively, equivalent to xץ/ץ( 1 xץ/ץ, 2 ) and ץ/ץ( 1 ץ/ץ, 2 ). To uncouple p 0 and p 1 the following local problems are considered in terms of the roughness coordinates and the auxiliary variables w 1 , w 2 , and w 3 ,

Ϫٌ •͑h 3 ٌ w 1 ͒ϭ ץh 3 ץ 1 Ϫٌ •͑h 3 ٌ w 2 ͒ϭ ץh 3 ץ 2 (8) ٌ .͑h 3 ٌ w 3 ͒ϭ⌳ ץh ץ 1
The boundary conditions for the local problems are that w 1 , w 2 , and w 3 equal zero on the boundary and are periodic functions.

The following relation is postulated to exist between p 1 w 1 , w 2 , and w 3 and the partial derivatives of p 0 :

p 1 ϭw 1 ץp 0 ץx 1 ϩw 2 ץp 0 ץx 2 ϩw 3 ϩC͑x 1 ,x 2 ͒ (9)
By substituting this expression in Eq. ͑5͒ and integrating with respect to , we obtain the homogenized Reynolds equation:

Ϫٌ•͓͑Aٌ͔p 0 ͒ϭٌ•͓͔ in the domain ⍀, p 0 ϭ0o nץ⍀ (10)
ͩ ͵ ⌶ h 3 ͩ 1ϩ ץw 1 ץ 1 ͪ d ͵ ⌶ h 3 ͩ ץw 2 ץ 1 ͪ d ͵ ⌶ h 3 ͩ ץw 1 ץ 2 ͪ d ͵ ⌶ h 3 ͩ 1ϩ ץw 2 ץ 2 ͪ d ͪ (11) ͓͔ϭ ͩ ͵ ⌶ ͩ h 3 ץw 3 ץ 1 Ϫ⌳h ͪ d ͵ ⌶ ͩ h 3 ץw 3 ץ 2 ͪ d ͪ
The notation of Eq. ͑11͒ is that we integrate the roughness variables ( 1 , 2 ) over their domain ⌶. Thus, one obtains the local problems ͓Eqs. ͑8͒ and ͑9͔͒ and the homogenized problem ͓Eqs. ͑10͒ and ͑11͔͒. These problems do not have analytical solutions, thus it is necessary to use numerical techniques.

Geometry of the Contact

Before carrying out the calculation of the homogenized pressure, it is necessary to define the geometry of the contact. The height of film can be written as

hϭh 0 ͑ x 1 ͒ϩ␦͑ 1 , 2 ͒ (12)
In turn, for demonstration, we use a parabolic cylinder contact

h 0 ϭh min ϩ x 2 2R (13)
This film shape is the parabolic cylinder approximation to a highly loaded journal bearing contact. All the characteristics of the contact have been nondimensionalized, and we use the following parameter values: h min ϭ1, ϭ1, Vϭ1, Rϭ1, ␣ϭ0.3 h min roughness amplitude, L x /L y ϭ1 ͑the ''unwrapped'' contact is rectangular͒. The roughness configurations have been obtained using the following roughness description:

␦ϭ␣ sin ͩ 2 L x 1 ϩL y 2 L x ϩL y ͪ ϭ␣ sin ͩ 2n r L x xϩL y y L x ϩL y ͪ (14)
In Eq. ͑14͒ above, L x ϭ1 and L y ϭ0 represents transverse roughness, L x ϭ0 and L y ϭ1 represents longitudinal roughness, with anisotropic roughness being characterized by intermediate values ͑see Fig. 3͒.

Results

We can see in Fig. 4 that the deterministic solution becomes erratic when the number of roughness cycles becomes significant. This is due to numerical error. Thus to have a well-behaved deterministic solution, it is necessary to increase the number of discretization points. However, we notice that the homogenized solution remains insensitive to this variation in roughness number.

We notice that for low roughness number, the deterministic solution remains far away from the homogenized solution ͑see Fig. 5͒. A reduction in the height of roughness peaks allows the two solutions to converge. Thus, this makes it possible to validate the model in the case of low amplitudes of roughness.

We observe the three-dimensional pressure field for n r ϭ40 and ␣ϭ0.3 h min in the homogenized and deterministic cases ͑see Fig. 6͒. We note that the direction of roughness is evident in the ho-

Conclusions

After analysis of the various results, we can draw several conclusions on this method of calculation. Homogenization makes it possible to obtain pressure fields for rough surfaces, using far fewer calculation points than for deterministic methods, while capturing important nonsymmetric features often missed by heuristic averaging. We note that the higher the period of roughness, the more the deterministic solution approaches the homogenized solution, which makes it possible to validate the model under the conditions where the number of roughness cycles is large.

For small roughness amplitude ͑compared to the minimum height of the film͒ and a significant number of roughness peaks, the homogenized analysis remains effective regardless of the type of roughness. Under these conditions this technique gives a good physical insight as to the distribution of pressure on the surface of contact. For anisotropic roughness, the technique of the homogenization is essential to give realistic information on the amplitude and the direction of roughness, contrary to the traditional ͑stochas-tic͒ approaches, which prove to be defective in this case.

Fig. 1

 1 Fig. 1 Comparison of roughness methodologies-dimensionless pressure

Fig. 3

 3 Fig. 3 Geometry of the global film thickness and roughness

Fig. 5

 5 Fig. 5 Dimensionless pressure profile variation with roughness number

Acknowledgment

The authors would like to thank Professor John Tichy who helped them in preparation of the manuscript while serving as a guest at INSA de Lyon.


Nelson Laracuente Montàs

Natasha Chayaamor-Heil

Biomimetic for Building Skin : Living Envelope for Contemporary Architecture

Keywords: biomimetic, biological system, architecture, smart materials, environment factors

come   L'archive ouverte pluridisciplinaire

Introduction

Recently, a great number of individuals working in areas of material engineering, architecture and design have attempted to distill the generative logics of 'natural systems' into their works. Bio-inspired processes are now integrating in diverse design methods and practices. Specific fields of interest such as biomimetics which delve into understanding such natural mechanisms and the application of the extrapolated knowledge into constructing performative structures, have since been at the heart of contemporary architectural and engineering researches. Biology is a discipline that can influenence design in unexpected and interesting ways. Especially, how environmental and climatic conditions have influenced the evolution of behavioral and physiological traits of animals can inform and inspire fields such as design and architecture. Adaptation strategies are considered to be a key aspect for the design of building envelopes that can accommodate the environmental changes with less energy consumption. It is proposed that the implementation of successful adaptation strategies inspired from nature can result in adaptive building envelopes that "behave" as living systems that accommodate the dynamic environmental changes; in other words, the envelope should be able to regulate and manage, among others, air, water, light and temperature. To this end, successful strategies could be obtained from nature, which presents an immense source for adaptation strategies [START_REF] John | Sustainable building solutions: a review of lessons from the natural world[END_REF] . The challenge for architects, in this context, is to transform these adaptation strategies from nature into successful technological solutions for building envelope. In this specific research, eleven animals have been chosen as rolemodels to inspire new material design, following three main reasons ; 1.Their skins are highly performative, 2.Their skins represent a direct response or adaptation to their environment, and 3.Their skins are important to their survival. We propose a strategic methodology that provides an exploration and investigation platform for architects. It assists channelling the way from biology to design and technical challenges, through functional aspects and various strategies found in nature.

Nature role models: Animals' skins and their adaptation solutions in nature

Living organisms' factors have necessitated the evolution of unique adaptations in terms of physiology, morphology, and behaviour [START_REF] Louw | Ecology of Desert Organisms[END_REF] ; the physiological and morphological adaptations reflect functional features that help organisms to adapt to their environment, whereas behavioural adaptations relate to the actions done by organisms in order to survive. Adaptation is especially obvious in the organisms able to survive harsh and challenging environment conditions, which include: extremes of temperature, lack of water, solar radiation, and other environmental factors. The term 'skin' refers to any animal covering, including fur, feathers, scales, exosckeletons, and shells. Skin is understood as an interface, transcending its surface, giving the appearance of something that separate, but instead acts as a threshold boundary, allowing for interaction with the elements in multiple directions, scales and timeframes. Architectural envelopes furnish great opportunities to take into consideration dynamic local environmental conditions, creating the potential to use the conditions as resources to be enhanced and supported rather than simply elements to conceal or overcome. Rigorous and systematic analyses of the performative aspects of the animal skin are the initial steps of the proposed methodology. An animal's skin can be extraordinarily complex and interactive system due to adaptive and responsive physiology through their climate and habitat data. Skin comes in all kinds of textures and forms, the main objectives are to understand the structure of the skin, the basic functions of the skin in sensing stimuli, temperature control and mechanisms. We have chosen eleven animals, which their skins can remarkably adapt to the changes in their environments, habitat and help the animals to survive. In general terms the three main threats to survival are temperature, lack of water and lack of food. Outside of environmental threats, many animals also need to be able to defend themselves or escape from predators in order to survive, lists of role models as following; The animals were chosen to reflect various types of skins from different climatic regimes. We focus on specific functions that were unique to the selected animals's skin. The biology of an animal and the environment it lives in determine these functions [START_REF] Sherwood | Animal Physiology: From Genes to Organisms[END_REF] . Investigating and analysing these strategies and their dominating principles are essential priors to the transfererability in design process.

Role model search, definition and paper references for scientific background

We start with the three main research areas ; science and technology as input, nature's principle as an abstraction for innovative design and architecture as an implementation. We developed a methodology and investigated the three areas and the role models through scientific papers. We create a data sheet for each animal to serve as working draft to present the underlying scientific information for the project and a system diagram to observe role models' phenomenas. 7 , e. Hygroscopic grooves between the spines of their skin, f. Water is conveyed to the thorny dragon's mouth by capillary action through a circulatory system on the suface of its skin, g. Diagram of hexagon structure. Right: a) Elytra structures of Physasterna cribripes (Namib desert beetle) [START_REF] Nørgaard | Fog-basking behaviour and water collection efficiency in Namib Desert Darkling beetles[END_REF] , b) A bumb and surrounding valleys [START_REF] Guadarrama-Cetina | Dew condensation on desert beetle skin[END_REF] , c) Dew phenomena on the dorsal surface 10 , d) Water dropet accumulmates on the dorsal, e) Exoskeleton ridges, f) Fog basking posture (23° from horizontal), exhibits a characteristic fog-basking head stand. This posture allows fog water collectd on the beetle's dorsel surface to trickle down to its mouth, g) Elytra (on dorsel) of all beetles were found to be completely hydrophobic, passively collect water from air 11 .

Building Envelope and Environment factors

Our research tackles the main question of how to generate design concepts for building envelopes that regulate environmental aspects, based on adaptation strategies from nature. Adaptation strategies are considered to be a key aspect for the design of building envelopes that can accommodate the environmental changes with less energy consumption. The successful strategies could be obtained from nature, which presents an immense source for adaptation strategies. The challenge for architects, in this context, is to transform these adaptation strategies from nature into successful technological solutions for building envelope adaptation.

Materials have a great influence on the performance of systems due to their molecular structure. The integration of advanced and responsive materials in building envelopes can enhance the adaptation in real-time for a better performance. A wide range of smart materials has been emerging throughout the last years, where it has a high potential in the construction field [START_REF] Addington | Smart Materials and Technologies: for the architecture and design professions[END_REF] . For example, phase change materials applied in buildings for energy conservation purposes improve thermal distribution and cost and space effectiveness. A new class of materials is being developed for potential use in buildings, e.g. the investigation of the use of shape memory alloys (SMA) and shape memory polymers (SMP) to realize a shape adaptable architecture for various purposes 13 , specially these smart materials can performatively behave like biological system.

Biomimetic Approach and Design Methodology

A major challenge of using biomimetics as a design tool is the filtering of the wide possibilities that nature provides, especially for architects who have limited biophysical background. The design generating tools should support the transitions between the domains, especially the identification of biological analogies and their abstraction. Biomimetics in architecture is an emerging field that develops further the interest of architects in role models from nature to a new discipline. The strategic approach differentiates biomimetics from mere inspiration from nature that has always existed in architecture. Bioinspiration transfers merely aesthetic and morphological aspects. Whereas in biomimetics, functional aspects play a key role. In general, materials, structures and processes from nature can find biomimetic transfers to new technical solutions. Although, nature provides a large database of adaptation strategies that can be implemented in biomimetic designs. Additionally, successful concept designs are limited, likely due to a number of factors beyond the ability to emulate nature's strategies to meet corresponding functional needs. Challenges in implementing biomimetic designs likely include: 1. the search for, and the selection of, an appropriate strategy or multiple strategies from the large database provided by nature, 2. scaling difficulties; strategies that work at one scale (e.g. nano) might not work at another (e.g. micro), and 3. built-ability in design phase. The selection of role models from nature is a common challenge facing architects. Processes, morphologies, and systems are all strategies available for mimicking, which can be implemented at various scales of results, e.g. material, element, building, and urban. From the literature 15 , two main approaches with various terminologies (B3.8 16 , BioT

) are noticed in biomimetics: 1. Biology to Design or 'solution-based', are inspired by an observation in nature which leads to a technological design, 2. Challenge to biology or 'problem-based', seek a solution from nature for a particular engineering problem. This project follows the first approach, where an observation in nature lead to a technological design innovation to solve particular problems, e.g. thermoregulation and water management in arid areas. This approach is taken to address the myriad challenges associated with adaptive building envelopes.

Analysis and evaluation matrix of role models aspects

The evaluation matrix was created as a knowledgebase and a selection tool, with the criteria delivering comprehensive information on the characteristic, performance and transferability of the chosen biological phenomena. Below the list of criteria used in the evaluation is presented. For most of the selected criteria quantitative data is not available. However, a qualitative statement estimating the importance of the criterion for the respective role model can be made. A simple differentiation between six qualities was used, from irrelevant-0, to very high-6. All role models were evaluated using the presented list of criteria. We first developed an understanding of the climatic characteristics of the environment in which the animal lives, followed by a study of the morphological and physiological strategies the animal uses to survive in its particular environment. After having an overview to each animal's adaptation we focus on animal's skin; the different layers, primary functions, how other physiological systems interact with the skin and how skin interacts with the environment. The analysis resulting of metrix evalution sheet aide in defining the stratification and functioning of the skin. Through this detailed analysis, a design lesson emerged, highlighting the fundamental elements of the skin and inspiration for the design of the living envelope. The design methodology selects dominant strategies that function simultaneously in nature. The proposed strategy consists of several phases and sub-phases, which are presented in unique flow charts that provide a selective user-friendly tool, which leads to a concept design of the living envelope. The new methodology provides a path for drawing design inspiration from nature. It considers architecture beyond the aesthetics or functional, and begins to explore the conceptually strategic. For architects and designers, it provides biological inspiration for further flexible and dynamic design, and templates for them to derive other species examples, an acts as a springboard for exploring broader applications beyond envelopes to applying whole ecosystems to entire building and communities. Five main considerations for living envelope concerning environment factors are; water, energy, thermoregulation, air, communication. The proposed methodology has to be selective in order to enable managing the large sample size nature provides. Thus, the methodology requires investigating adaptation strategies and mechanisms found in nature, and distinguishing various functional aspects relevant for adaptation, which are classified in an exploration model and selective design tools leading to the generation of design concepts for building envelopes. The flow chart tools increase the efficiency of the design process, and they are capable to generate design concepts with a specified initial challenge set by the user. Moreover, the design cases opened new perspectives for new possible technical solutions for building envelopes, and the potential to realize a new class of innovation and lay a functional foundation in architecture: a bio-inspired, climatically oriented, and environmentally conscious.

Design Methodology

Material Design

We realise that nowadays, water shortage is a severe issue all over the world, especially in some arid and undeveloped areas. Interestingly, from a variety of animals' skins selected can collect water from fog, which can provide a source of inspiration to develop novel and functional water-collecting materials. The theoretical basis related to the phenomenon of water collection containing wetting behaviors and water droplet transportations is described in desert animals in the initial biological observation, ie., the thorny devil's skin has funtional system with Hygroscopic grooves (absorbing moisture from air) and the ability to passively transport water through capillary system to its mouth. The namib desert beetle's skin collects water from fog by condensation on the elytra (fog-basking behaviour), also a special arrangement of hydrophilic and hydrophobic areas on the elytra results in attracting water droplets and transporting it to the mouth. Then, the water collection mechanisms of the desert animals are discussed and their corresponding bioinspired materials are simultaneously detailed. Finally, conclusions and outlook concerning the future development of bioinspired fog-collecting materials are presented.

'Hygro-NET' fog-harvesting material design

'Hygro-NET', is a bio-inspired fog-harvesting material design that abstracts the strategic methods from the desert animals, Thorny dragon and Namib desert beetle, how their skins perform to collect and supply water in arid climate. We transfer this process of passive water transport system and dew condensation to improve the efficiency of the fog-harvesting material design. The suggested component materials were the following; 1) Acrylonitrile butadiene styrene (ABS) plastic, to be used as structural, cohesive framework providing stability and integrity and also serve as condensed water drivers aided by gravity, mimicking "capillary action", these should be fabricated using a 3D printer. 2) Alkaline Hydrolyzed Polyacrylonitrile (HPAN) super absorbent polymer fibers to actuate as a hygroscopic attractor, as defined and fabricated by Xiaoyu Hu and Changfa Xiao [START_REF] Hu | Superabsorbent Polyacrylonitrile Based Fiber[END_REF] and investigated by Mark González [START_REF] Gonzalez | An Investigation of electrochemomechanical actuation of conductive polyacrylonitrile (PAN) nanofiber composites[END_REF] . 3) Nickel-Titanium alloy (Flexinol Muscle wire brand sold by robotshop and manufactured by DYNALLOY) to be used as HPAN enhancers, actuator components.

The structural frame of the hexagon cell, abstracted from the pattern of honeycomb-shaped showing all over scales of the Thorny dragon, is made of Acrylonitrile butadiene styrene (ABS) plastic. The material is hydrophobic, it's efficiency for condensing and trasporting water. The hexagon grid is 30mm in diameter (which could be reduced, in theory, but data cost of augmenting its hygroscopic efficiency, yet exponentially increasing fabrication difficulty and expensiveness). The scaling up problem is addressed with 5 x 5 cell "patches" that can be attached, sewn to each other or mounted on different, fixed scaffolding structures, curtainwalls or frames and could populate large surfaces or relatively small empty spaces on their own (like ducts or windows). During this research project, we drew a parallel and mimic between the Thorny devil's hygroscopic system and the namib desert beetle's fog-basking behaviour to a synthetic, super absorbent polymer (SAP), itself hydrolyzed by alkaline solutions, which can absorb about >10 times its own weight, called Polyacrylonitrile (HPAN) (accurate water absorbency of 40g/g). [START_REF] Hu | Superabsorbent Polyacrylonitrile Based Fiber[END_REF] From the start, it was clear that, though the material does exhibit remarkable properties, the possibility of a similar result in terms of efficiency was not foreseen as a probable one, because the HPAN works with already condensed water and itself does not transport it to a usable place. Then, for the fiber to work in almost any climatic condition, the combination of two materials actuating together in an open-close transition logic to enhance HPAN's properties was proposed as a sensible solution. Our hypothesis was simple: HPAN would be relaxed (at about 2mm's distance) when the temperature would be lower than 90c° (therefore Ni-Ti would be in shape A (a strand), in order to absorb more water than HPAN would on its own. Later to be pulled back to its tension state (when the temperature would go over 90c°) by Ni-Ti's programmed actuation into shape B (a spring) in order to expel and percolate the condensed water inside the HPAN's porous fibers. [START_REF] Gonzalez | An Investigation of electrochemomechanical actuation of conductive polyacrylonitrile (PAN) nanofiber composites[END_REF] The proposed Ni-Ti alloys in this paper were selected from a commercially available and hold a transition temperature of 70c° to 90c° so, under normal thermal conditions, they have to be actuated by electricity (very low voltages ranging between 20 and 4000 Milliamps). Yet in an extreme environment like a desert, they could work without electrical stimuli thanks to heat conduction and accumulation alone. In theory it is possible to engineer and design alloys that work at lower temperatures but, since they're not commercially available and this poses a constraint in terms of fabrication hence our decision to simulate commercially available ones just to establish general principles that can be later adapted to specific, custom alloys and cases.

Conclusion

The greatest challenge faced by biomimetics is to determine how nano [START_REF]Nano refers to one thousandth of one millionth. 1000 million nanometers are one meter. A human hair is about 70 000 Nanometers thick. Nanoscience and -technology deals with functional structures on a length scale of some tens to some hundreds of nanometers[END_REF] and microstructures function in their relationship with the organism and the environment, especially if these have not been fully explored yet. As in nature, where design develops from small to large scale, the material design should also develop in the same manner as in nature to meet specific building and environmental criteria, acting as design targets to be achieved. The Simulations show that the textile composite should work as required in accordance with the animal skin selection process. Performance in terms of mechanical data and built-ability remain to be tested yet the evidence stongly suggests that the hygroscopic component should have a significant accurate working proefficiency. This research project can conclude that mimicking animal skin depends on the case at hand (both in term of building and biology) yet a methodology can and has been established as a guideline for the decision making process and its subsequent design and implementation process. The results show that, not only is transferring animal skin properties to building "skin" possible and interesting design wise, but that it will enhance our ability to invent ever more complex and efficient façade, building envelope systems and environmental mediation devices while also embedding intelligence and will draw us close to autonomous,self-regulating buildings that could, one day, be bred, "grown" and totally biodegraded into new bio-architecture.

!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

Biography

Nelson Montás, from Santo Domingo, Dominican Republic, holds an architecture degree from the Universidad Nacional Pedro Henríquez Ureña's School of Architecture and Urbanism (2006) in Santo Domingo, Dominican Republic, where he is a registered architect (CODIA 25715) and has practiced the profession since. He also holds a Master of Science in Biodigital Architecture from the ESARQ at the International University of Catalonia (2009) where he also recently fulfilled requirements for Ph.D. accreditation. He is also a visiting researcher at the Ecole Nationale Supérieure d'Architecture Paris -La Villette where he is carrying out research on Shape Memory Materials simulations using parametric tools, under the guidance François Guéna, Ph.D. As a freelance architect with a civil engineering background, he has been a designer, evaluator and construction supervisor at the Potable Water and Sewage Systems Institute in the Dominican Republic. He has also been involved in teaching, namely at the Pontificia Universidad Católica Madre y Maestra's School of Architecture and is involved in active research. (arq.montas@gmail.com) Natasha Heil, is an architect and a researcher at MAP-Maacc, CNRS-MCC UMR 3495, ENSA PARIS-La-Villette, Paris, France (http://www.map.archi.fr). She has obtainted her ph.D in Biomimetic approaches in design and innovation. Her research is to explore the relationships between nature's principles and architectural design, by which using biology influences design along with advance science and technology as inputs towards sustainability; this interdisciplinary approach is known as biomimetic or biomimicry. She seeks to instill a shift in thinking about the application of biological principles to design and architecture. Her researches focus on the methodology to absctract nature's principles and transfer natural systems to architectural design. She also developes the analysis of how organisms have adapted to different environments and translates the learned principles into the built environment. (natasha.heil@outlook.com)

NEW MATERIALITY IN CONTEMPORARY ARCHITECTURAL DESIGN

Biomimetic for Building Skin Living

ENVELOPE FOR CONTEMPORARY ARCHITECTURE

As a highly interdisciplinary fi eld, architecture is being infl uenced by many subjects of natural and social sciences. While many subjects hold an indisputable eff ect on architecture, biological sciences are currently dominating the current era. It is totally comprehensible for architects to observe and imitate the natural phenomena on behalf of a better living. This article will present how to translate the lessons learned from the analysis and observation of the animal world to design experience. Skin is a complex and incredibly sophisticated organ that performs various functions, including protection, sensation, insulation, temperature and water regulation. The skin interfaces with the environment and is the fi rst line of defense from external factors. Similarly, building envelopes serve multiple roles and they are the interface between the building inhabitants and environmental elements.

In architecture, the boundaries between materials and structures are blurred the same way as in nature. The study of biological systems might be useful for our purposes on how new materials can be designed. The new material is inspired by the study of how animal skins perform and respond according to their diff erent properties; they take into consideration various dynamic local environmental conditions, creating a more sustainable way of building hence living. The projects will be focused on specifi c functions that were unique to the selected animal's skin. The biology of an animal and the environment it lives in determine these functions. The processes by which each animal analysis will be carried out, will innovate in the design and conception of new materials. Which will, in turn, inform new synthetic designs based on biological systems that will describe new aspects and performance of the building envelope.

Figure 1 .

 1 Figure 1. System diagram analysis. Left: a. Moloch horridus 4 (Thorny dragon), b. skin cross section from single OCT slide 5 , c. SEM-image of capillary opening between the dorsal scales 6 , d. The skin shows the honeycomb like micro ornamentation virtually all over all scales7 , e. Hygroscopic grooves between the spines of their skin, f. Water is conveyed to the thorny dragon's mouth by capillary action through a circulatory system on the suface of its skin, g. Diagram of hexagon structure. Right: a) Elytra structures of Physasterna cribripes (Namib desert beetle)[START_REF] Nørgaard | Fog-basking behaviour and water collection efficiency in Namib Desert Darkling beetles[END_REF] , b) A bumb and surrounding valleys[START_REF] Guadarrama-Cetina | Dew condensation on desert beetle skin[END_REF] , c) Dew phenomena on the dorsal surface 10 , d) Water dropet accumulmates on the dorsal, e) Exoskeleton ridges, f) Fog basking posture (23° from horizontal), exhibits a characteristic fog-basking head stand. This posture allows fog water collectd on the beetle's dorsel surface to trickle down to its mouth, g) Elytra (on dorsel) of all beetles were found to be completely hydrophobic, passively collect water from air 11 .

14

 14

Figure 2 .

 2 Figure 2. Scheme of the approach towards the living envelope: convergence of the building envelope's challenges with nature's survival strategies (animals' skins) through biomimetics.

Figure 3 .

 3 Figure 3. Evaluation sheet: Intersection of the properties of animals' skins and architectural design.

Figure 4 .

 4 Figure 4. The unique flow chart methodology leading to a concept design of the living envelope.

  Photosynthesis

Figure 5 .

 5 Figure 5. Hygro-NET system diagram, fog-harvesting material that behaves as functional living system.

Figure 6 .

 6 Figure 6. Left: Simulation and Physical Properties: A Single component's performance simulations to study Alkaline Hydrolyzed Polyacrylonitrile (HPAN) behavior with Ni-ti alloy as actuator components going from tension to relaxation. Simulation executed using Rhinoceros 5.0 + Grasshopper version (0.9.0076) + Kangaroo (version 0.099). Right: Test 3D-printing prototype of a 5 X 5 cell -patches 25 .

  NATASHA HEIL MAP-Maacc, CNRS-MCC UMR 3495, ENSA PARIS-La-Villette, Paris, France natasha.heil@outlook.com NELSON LARACUENTE MONTÀS Universitat Internacional Catalunya, Architecture Dep., Barcelona, Spain, arq. montas@gmail.com

  01. Giraffa camelopardalis (Giraffe); Survive the heat in Africa 02. Hippopotamus amphibious (Hippos); Survive in dry-tropical climate 03. Crocodylus niloticus (Crocodile); Survive to find food (pray) and suitable habitats 04. Acomys kempi and Acomys percivali (African spiny mouse); Survive from predators 05. Cephalopoda (Inkfish); Survive from defensing against predators 06. Acrochordus granulatus (File snake); Survive from humid-hot climate 07. Moloch horridus (Thorny dragon); Survive from lack of water in dry desert 08. Barbourula kalimantanensis (Bornean flat-headed frog); Survive from having no lungs

	09. Elysia chlorotica (Green sea slug); Suvive without nutrition for long period
	10. Penguin feather; Survive from extreme cold
	11. Physasterna cribripes (Namib desert beetle); Survive from lack of water in dry desert