text:
# Non-intrusive on-the-fly data race detection using execution replay.11footnote 1In M. Ducassé (ed), proceedings of the Fourth International Workshop on Automated Debugging (AADEBUG 2000), August 2000, Munich. COmputer Research Repository (http://www.acm.org/corr/), cs.SE/0011005; whole proceedings: cs.SE/0010035.

## 1 Introduction

The never ending urge for faster and more robust computers, combined with the existence of cheap processors causes a proliferation of inexpensive multiprocessor machines. Multithreaded applications are needed to exploit the full processing power of these machines, causing a widespread use of parallel applications. Even most contemporary applications that are not CPU-intensive are multithreaded because the multithreaded paradigm makes it easier to develop servers, applications with an MDI (multiple document interface) such as Windows programs, etc.

However, developing multithreaded programs for these machines is not easy as it is harder to get a good view on the state of a parallel program. This is caused by the fact that there are a number of threads222In this paper we will consider an execution of a parallel program as being a process consisting of $`N`$ threads executing on a machine with $`N`$ processors. running simultaneously. Moreover, the very fact that the computation is split into simultaneous parts can introduce errors that do not exist in sequential programs. These synchronisation errors show up because parallel programs are developed in order to let a number of threads work on the same problem, hence they will share data. It is of paramount importance that the accesses performed by the different threads are properly synchronised. Too much synchronisation will deadlock the program, while a lack of synchronisation will lead to race conditions. Such a race condition occurs when two or more concurrently executing threads access the same shared memory location in an unsynchronised way, and at least one of the threads modifies the contents of the location.

The program depicted in Figure 1 is an example of a program containing a race condition. The program uses a shared global variable (global), initialised with value 5. The first thread (main) starts two additional threads, t1 and t2, executing respectively the functions thread1 and thread2. Both threads change the global variable. As the threads do not synchronise, the final value of global will be 18, 11 or 12. The latter two are the result of one of the threads overwriting the new value written by the other thread.

As race conditions are (most of the time) considered bugs, they should be removed. Unfortunately, race conditions are difficult to find because their occurrence depends on small timing variations. Although it is possible to detect race conditions using a static approach (using source code analysis, as done by ) this is not feasible for nontrivial programs (it has been shown that detecting race conditions statically is an NP complete problem for programs that use synchronisation that is powerful enough to implement mutual exclusion ). Therefore, most race detection tools detect race conditions dynamically during an actual program execution.

In this paper, we present and describe RecPlay, a tool that detects data races (data races are harmful race conditions; see next section) dynamically. RecPlay was implemented for the Solaris operating system running on Sun multiprocessors with SPARC processors. During the test phase of RecPlay, we have found data races in several programs we tested (including the SPLASH-2 suite , and the Athapascan system ). All of the races that were reported were genuine data races that had stayed undetected until then.

In the next section, we start with a few definitions about race conditions followed by a description of data race detection techniques. The section ends with an overview of our method. The next section describes our implementation. This part is followed by an evaluation section containing performance data. The paper is concluded with an overview of related work.

## 2 Data races

### 2.1 Definitions

A race condition occurs when two threads access the same shared location in an unsynchronised way and at least one access modifies the value at the location. We distinguish two types of race conditions: race conditions that are used to make a program intentionally nondeterministic: synchronisation races, and race conditions that were not intended by the programmer (data races).

We need synchronisation races to allow for competition between threads to enter a critical section, to lock a semaphore, or to implement load balancing. Removing synchronisation races makes a program completely deterministic. Therefore, in this paper, we do not consider synchronisation races a programming error, but a functional and useful characteristic of a parallel program.

Data races are not intended by the programmer, and are most of the time the result of improper synchronisation. By changing the synchronisation, data races can (and should) always be removed333There are a few applications that use data races intentionally, e.g. relaxation algorithms..

It is important to notice that the distinction between a data race and a synchronisation race is actually a pure matter of abstraction. At the implementation level of the synchronisation operations, a synchronisation race is caused by a genuine data race (e.g., spin locks, polling, etc.) on a synchronisation variable.

If the programmer creates his/her own synchronisation operations, we also have to make a distinction between feasible races and apparent races. The difference between them can be intuitively understood from the following example.

| thread1 | thread2 |
| --- | --- |
| result=x; | while (done==FALSE); |
| done=TRUE; | y=result; |

Technically speaking, in this fragment, there are no explicit synchronisation operations, and therefore, a naive race detection will detect two races: one on result and one on done. However, after taking the semantics of the program fragment into account, there is only one data race that can actually occur, namely on done because the data race on result cannot occur, provided that done was set to FALSE before the two threads were created.444This is true if the computer has a memory model that guarantees at least processor consistency. Modern processors with weaker memory models require some kind of serialisation instruction (e.g. a STBAR instruction on a SPARC) between the two store operations performed by the first thread to make this work correctly. This example only serves to explain the concept. We say that his program fragment contains two apparent data races, but only one data race is feasible.555All synchronisation races should be feasible races. A synchronisation race that is apparent but not feasible is an indication that the synchronisation is superfluous.

### 2.2 Detecting data races dynamically

As mentioned before, a dynamic data race detector finds data races that occur during a particular execution. In order to detect the conflicting memory operations, one should collect all memory operations executed during a particular execution and information about their concurrency. The concurrency depends on the (order of the) executed synchronisation operations. By analysing the traced information one can find the data races that occurred during that particular execution. However, this type of post-mortem approach is not feasible due to the very large trace files that have to be generated. However, by carefully examining the requirements for data race detection it is possible to limit the information that has to be traced without sacrificing the efficiency of the detection.

There exists basically two (dual) methods for detecting data races using collected memory and concurrency information:

* for each access to a global variable, the access is compared against previous accesses by other threads to the same variable. This requires us to collect, for each global variable, information about past accesses666It suffices to collect information about the last load and store operation of each thread.. It is obvious that this will lead to a huge memory consumption, especially if each memory location is a potential global variable with life time equal to that of the program itself, as is the case for e.g. programs written in the $`C`$ language.
* for all parallel pieces of code, the memory operations are collected and compared. This method consolidates the fact that all memory operations between two successive synchronisation operations (called segments from now on) satisfy the same concurrency relation: they are either all concurrent or not concurrent with a given operation.

Given the sets $`L(i)`$ and $`S(i)`$ containing the addresses used by the load and store operations in segment $`i`$, the concurrent segments $`i`$ and $`j`$ contain racing operations if and only if

$$\left(\left(L(i)S(i)\right)S(j)\right)\left(\left(L(j)S(j)\right)S(i)\right)\mathrm{}$$

Therefore, data race detection basically boils down to collecting the sets $`L(i)`$ and $`S(i)`$ for all segments executed and comparing parallel segments.

It is clear that the second method is better suited for programming languages with unconstrained life time of and access to shared variables. However, two problems remain:

1. treating all memory accesses the same way prevents us from making a distinction between the synchronisation (due to the memory accesses performed by the synchronisation operations) and the data races;
2. collecting all memory operation introduces a huge overhead, both in time and space. The unavoidable intrusion gives rise to the probe effect, possibly causing Heisenbugs.

The last problem is a dramatic problem, as it seems unsolvable. Indeed, we cannot circumvent the tracing of all memory operations if one wants to detect data races. However, it is possible to alleviate the problem by tracing an application in two phases.

### 2.3 Data race detection using two phases

Data race detection using two phases detects data race in a programn execution using two ‘equivalent’ executions:

1. synchronisation races are dealt with during the first phase. During this record phase a limited amount of information about the execution is traced;
2. during the second phase, all the information needed to detect data races is traced, and the information traced during the first phase is used in order to guide the second execution. This execution is guided in order to enforce the execution to be equivalent (two executions are said to be equivalent if they yield the same internal program flow) with the first execution.

In order to be able to force an execution to be equivalent with another execution, information about the ‘decisions’ that (could) have an impact on the program flow of the first execution should be traced. This information is:

* input received from sources outside the process such as reading from disk, system calls such as gettimeofday(), random(), …This paper will assume that all input can be fed back during a replayed execution, either because the input is on stable disk or is replayed, e.g. by intercepting system calls;
* ‘input’ received from other threads that are part of the same process777In this paper, we only deal with parallel threads belonging to one process. Different processes exchanging data (e.g. using mmap()) are not considered.. Indeed, as each load operation possibly reads a value written by another thread this should be considered input. Note that these are the race conditions mentioned before.

It seems that this does not solve our problem: we have to trace all memory operations in order to get a faithful re-execution, making it impossible to get a trace of an execution that is not perturbed. However, tracing all race conditions is not necessary. If we only trace the synchronisation races, a correct re-execution is only possible in the absence of data races. If the execution contains one or more data races, the re-execution will (possibly) fail after the data race starts having an effect on the execution. As the point at which the data race starts effecting the execution occurs after the occurrence of the data race itself, it is possible to detect the data race during the guided re-execution.

Using two phases has a number of benefits:

* the overhead introduced during the record phase will be small as:

+ the number of synchronisation operations is usually much smaller than the total number of memory operations,
    + we can trace a synchronisation operation as being a single operation, although the synchronisation operation will typically perform (e.g. in a spinning loop) a number of memory operations,
    + making a distinction from the beginning between synchronisation races and data races makes it easier to detect only the data races during the replay phase,
* it is easy to trace the synchronisation operations as they are usually implemented in a dynamically linked library, making it possible to intercept them by interposing an instrumented library.

This solution allows us to perform an intrusive data race detection during a ‘normal’ re-execution. The price we have to pay is that we need two executions in order to collect all the information.

Although this solves part of our problem (the intrusion is limited), this is not a viable solution as we still need to collect a lot of information during the replayed execution. However, it is possible to limit the amount of information we need to collect in other to find data races.

### 2.4 Limiting the amount of traced information

A naive tool could perform the data race detection post-mortem, forcing us to collect all information in memory or on disk. However, if an execution contains a data race, there is no need to keep looking for other data races. Indeed, due to the so-called avalanche effect, the first data race should be removed before the others. Moreover, as soon as (the effects of) a data race occurs, the replayed execution is no longer guaranteed to be correct. On-the-fly detection is therefore a viable alternative: data race detection is performed during the execution, and as soon as a data race is found, information about it is displayed. This method will use less memory if a data race shows up near the start of the program. However, a program execution with a data race near the end, or with no data race at all, will still use a huge amount of memory as this approach keeps on adding $`L(i)`$ and $`S(i)`$ sets to memory. It is therefore important to remove them as soon as it is clear that there are no more segments that will need them for future comparison. A segment can be removed if all other threads have progressed beyond the point in logical time when the segment did terminate. After that point in time, there can be no more segments started that possibly cause a data race.

If a program execution contains a data race, the programmer is interested in the racing instructions and the variable they race on. Therefore, we have to collect the address of the instruction and the address of the variable used for every memory operation contained in a segment. However, as this amounts to a huge memory consumption, RecPlay only stores the addresses used and no information about the instructions themselves. This information is sufficient to detect data races, but not the offending instructions. A third execution (identification phase) is needed to locate these instructions. During this execution, the knowledge about the data race (address of the variable, identities of the threads, the identity of the segment and type of operation (load or store)) is sufficient to locate the actual racing instructions.

The online data race detection is therefore performed by RecPlay using three phases:

1. record phase: trace all synchronisation operations,
2. replay & detect phase:

* for each executed memory instruction: trace the address used,
    * for each synchronisation operation executed:

    + make sure it is executed at the right moment: between the same two synchronisation operations as during the recorded execution,
        + compare the traced memory operations of the ended segment with previously executed parallel segments. If a data race is found: end the program,
        + add the collected information ($`L(i)`$ and $`S(i)`$) to the list of segments,
        + remove obsolete segments from the list,
3. if a data race was found: identification phase.

In the next section, the techniques used to implement RecPlay are discussed.

## 3 Implementation

As mentioned in the introduction, our method has been implemented for Solaris. Our tool RecPlay will detect the first feasible data race in an execution as long as the application under test only uses the Solaris (or POSIX) synchronisation operations. This still applies if one builds own synchronisation operations (or uses a third party library) on top of the Solaris or POSIX variants.

Data races detected in user programs that also use their own synchronization operations can also be apparent data races that are not feasible. However, at least one of the apparent data races must be a feasible data race  that is used to synchronize the other memory references (and hence is a synchronization race). By replacing user defined synchronization operations by Solaris synchronization operations, or by putting the new synchronization operations in a separate library that is flagged as synchronization library, we can prevent RecPlay from detecting such synchronization races during subsequent runs.

### 3.1 Instrumentation

In order to collect the memory reference information and to record/replay the synchronisation operations, RecPlay intercepts these operations using JiTI (Just in Time Instrumentation, ). JiTI was developed for RecPlay but is a general instrumentation technique able to deal with hard to instrument features such as code in data, data in code and self modifying code.

The two major difficulties when inserting code into binaries are (i) correctly distinguishing between code and data (especially when code is located in data, when data is located in code, or when self-modifying code is used) and (ii) correctly relocating the code and data after inserting instrumentation code.

In existing systems, these two difficulties can only be solved by applying a sophisticated analysis (disassembling the program into basic blocks and control flow graphs) of the binary. Hereby, assumptions have to be made about the origin of the code. Most systems can be broken by offering hand-written machine code to it. A careful analysis for large programs can take a inordinate amount of resources (both in time and space).

JiTI solves these problems (i) by creating two versions of the process: one for the data accesses and one for the code accesses and (ii) by not inserting instrumentation code in the process, but by replacing instructions by calls to instrumentation code. By cloning a process and by executing the code from an (instrumented) copy, and using the data from the other copy, we get rid of the need to distinguish between code and data.

Given the size $`\alpha `$ of the original process, a clone is created at address $`\delta `$ ($`>\alpha `$) (up to address $`\delta +\alpha `$). Since we do not insert instructions, but only replace instructions, the instrumented version of the instruction at address $`i`$ will reside at address $`\delta +i`$.

We now have access to two copies: one copy that is entirely considered as data, and another copy that is entirely considered as code. In order to make sure that data is taken from one copy, and the code from the other copy, we will have to modify addresses that do not point to the right copy (by increasing or decreasing them with $`\delta `$). It turns out that addresses used to access data are mostly absolute data addresses, while, on contemporary microprocessors, code addresses are mostly relative addresses (position independent code). Since relative addresses do not require relocation when moved to another location in memory, the best choice is to fetch the code from the clone, and the data from the original copy of the process. This means that the relocation effort can be limited to the rare –especially on a SPARC processor– absolute code addresses (to make sure that the execution will never jump back to the non-instrumented version of the process888Some instructions that are known to make use of correct absolute addresses (such as returns), do not need to be instrumented.) and to the rare code-relative data addresses that might be used in the code (e.g., for data that is located in the code, such as address tables).

In these cases where the relocation cannot be done at clone time (e.g. for memory operations, where it is impossible to distinguish the memory operations that use relative addresses from those that use absolute addresses), it suffices to check the addresses on-the-fly by instrumenting the instructions that make use of them. The instrumentation of the clone can be performed before the program starts or during the execution (by filling the clone with trapping instructions and by instrumenting an instruction (or a whole page) whenever an instruction is executed for the first time). It is even possible to have different clones (for parallel programs) with different instrumentation for different threads. It is also possible to change the instrumentation during the execution. This can be used to deal with self-modifying code: store instructions are instrumented to write the data to the original and a trap instruction to the clone. If the trap instruction is ever executed, JiTI intercepts the trap and instruments the instruction (if necessary). By having the instrumentation code do further instrumentation, the instrumentation can modify itself dynamically.

JiTI is also able to intercept dynamically linked library calls, and does not instrument the memory operations in these libraries. This is ideal for making a distinction between synchronisation and data races: all Solaris synchronisation operation are contained in a dynamically linkable library.999The library has no static variant, as is the case for most of the system libraries. As such, the many memory operations that are used by the synchronisation operations are not seen.

RecPlay and JiTI have been implemented for Sun multiprocessors running Solaris 7. The implementation uses the dynamic linking and loading facilities of the operating system. A number of dynamic loadable libraries have been created: one records the order of the synchronisation operations, another one detects data races during a replayed execution, and the last library identifies the offending references while replaying a previously recorded run. Using an environment variable, the Solaris program loader is forced to load one of these libraries each time it loads a user program. The libraries contain the necessary routines to perform initialisation before the actual program starts. Neither the user program nor the thread library needs to be modified as the RecPlay library inserts itself automatically between the user program and the thread library. This is because we want to keep the RecPlay operation (record, replay, race detection, reference identification) a feature of an execution, rather than a feature of a program.

### 3.2 Tracing and replaying the order of the synchronisation operations

In previous work, we have developed ROLT (Reconstruction of Lamport Timestamps), an ordering-based record/replay method, where only the partial order of synchronisation operations is traced by means of (scalar) Lamport clocks attached to these operations. To get a faithful replay, it is sufficient to stall each synchronisation operation until all synchronisation operations with a smaller timestamp have been executed. The execution traces consist of a sequence of timestamps, one trace per thread. The method  has the advantage that it produces small trace files (it is not necessary to log all timestamps) and that it is less intrusive than other existing methods . Moreover, the method allows for the use of a simple compression scheme  which can further reduce the trace files.

### 3.3 Collecting and comparing the addresses of the memory operations

As mentioned before, two lists of addresses are used for every segment $`i`$: the load operations are collected in $`L(i)`$ and the store operations in $`S(i)`$.

These addresses are collected in a bitmap (one for each list). Such a bitmap contains a $`1`$ on place $`i`$ if address $`i`$ was used. As a linear bitmap would require $`2^{32}/8=512`$ MB, a multilevel bitmap is used (see Figure 2).

The multilevel bitmap uses three levels: two levels containing page tables and one level containing the actual bitmaps. The highest level is addressed using the 9 highest bits of the addresses. This level contains pointers to page tables at the second level. These page tables are indexed using the next 9 bits and contain pointers to the actual bitmaps. The actual bitmaps are indexed using the remaining 14 bits of the address. Indexing the multilevel bitmaps using a 9/9/14 scheme results in page tables and bitmaps of 2kB. This makes the frequent allocating/deallocating of these data structures simple enough to implement it ourselves without reverting to malloc()/free(). Measurements show that this speeds up an execution with about $`10\%`$.

Although the use of a bitmap means that some information is lost – two or more accesses of the same address are counted as one – this is not a problem for data race detection. Indeed, if one of these accesses is involved in a race, the subsequent accesses are also involved in a data race. The use of multilevel bitmaps makes it possible to compare the segments in an efficient way.

### 3.4 Detecting and comparing parallel segments

In our race detection tool, we use a classical logical vector clock  to detect concurrent segments (left part of Figure 3). Updating vector clocks is time-consuming, but this is not an issue during replay. As vector clocks are able to represent the happened-before  relation (they are strongly consistent), two vector clocks that are not ordered must belong to concurrent segments. This gives us an easy way to detect concurrent segments.

### 3.5 Detecting Obsolete Segments

Logical matrix clocks  are traditionally used to discard information in a distributed environment: the componentwise minimum of the columns yields the maximum number of segments per thread that can be discarded (right part of Figure 3.

However, in practice we can discard more information than is indicated by logical matrix clocks as logical clocks capture causality, which is one of the weakest forms of event ordering. In a particular execution, all events are executed is some order (not specified by the program), even if they do not have a causal relationship. Classical logical clocks are not able to capture this kind of additional execution-specific ordering.

Our data race detection method uses clock snooping . Instead of maintaining matrix clocks, a snooped matrix clock is built each time a segment ends, using the latest vector clock of the processors. All segments that have a vector clock smaller than the componentwise minimum of the snooped matrix clock can be discarded as they will not be needed in the future anymore.

In Figure 4, we show the information we obtain by the two brands of matrix clocks. It is clear that a snooped clock allows to discard more segments than a classical logical clock. Figure 5 compares the behaviour of logical and snooped matrix clocks.

### 3.6 Identification Phase

Once a data race is found using the scheme described above we know the address of the location and the segments containing the offending instructions, but not the instructions themselves. Detecting these instructions requires another (deterministic) replay of the program. This operation is completely automatic however and incurs no large overhead. The replayed execution runs at full speed up to the segments that contain the data race and from then on the instrumentation is switched on and the offending instruction is searched for. We are always guaranteed to find the first data race on a particular variable.

## 4 Experimental evaluation

Tables 1-3 give an idea of the overhead caused by RecPlay during the record and the detection phase for programs from the SPLASH-2 benchmark suite. The experiments were performed on a Sun multiprocessor with 4 processors. The average overhead during the record phase is limited to 2.1% which is small enough to keep it switched on all the time. The automatic race detection is however very slow: it slows down the program execution about 30 times. Remember that the intrusion caused by this huge overhead does not alter the execution, as this is a replayed execution.

The cause of this huge overhead is explained in Table 2 where the number of segments and memory accesses is shown. Apparently, for most of the test programs, the execution of the instrumented memory operations is the critical speed factor. For these benchmarks, this is about 350 000 memory operations per second. Cholesky, raytrace and ocean do not reach that number, caused by the fact that a lot of segments are compared during the race detection. With regard to the number of segments stored, we see that the matrix clock algorithm indeed succeeds in substantially reducing the number of segments that have to be stored, limiting the memory consumption of the race detector.

Table 3 shows why the overhead of recording an execution is limited to about 2%. This is because ROLT effectively succeeds in creating small trace files. The disk bandwidth needed to store the trace is never bigger than 4 kB/s, which is very low on modern machines. On the average, we only need to store about 2.3 bits per synchronisation operation.

## 5 Related Work

Although much theoretical work has been done in the field of data race detection  few implementations for general systems have been proposed. Tools proposed in the past had limited capabilities: they were targeted at programs using one semaphore , programs using only post/wait synchronisation  or programs with nested fork-join parallelism . The tools that come closest to our data race detection mechanism, apart from  for a proprietary system, is an on-the-fly data race detection mechanism for the CVM (Concurrent Virtual Machine) system . The tool only instruments the memory references to distributed shared data (about 1% of all references) and is unable to perform reference identification: it will return the variable that was involved in a data race, but not the instructions that are responsible for the reference.

Race Frontier  describes a similar technique as the one proposed in this paper (replaying up to the first data race). Choi and Min prove that it is possible to replay up to the first data race, and they describe how one can replay up to the race frontier. A problem they do not solve is how to efficiently find the race frontier. RecPlay effectively solves the problem of finding the race frontier, but goes beyond this. It also finds the cause of the data race.

Most of the previous work, and also our RecPlay tool, is based on Lamport’s happened-before relation. This relation is a partial order on all synchronisation events in a particular parallel execution. Therefore, by checking the ordering of all events and monitoring all memory accesses, data races can be detected for one particular program execution.

Another approach is taken by a more recent race detector: Eraser . It goes slightly beyond work based on the happened-before relation. Eraser checks that a locking discipline is used to access shared variables: for each variable it keeps a list of locks that were held while accessing the variable. Each time a variable is accessed, the list attached to the variable is intersected with the list of locks currently held and the intersection is attached to the variable. If this list becomes empty, the locking discipline is violated, meaning that a data race occurred. Unfortunately, Eraser detects many false data races: as Eraser is not based on the happened-before relation it has no timing information whatsoever. For instance, in theory there is no need to synchronise shared variables before multiple threads are created. The happens-before relation deals in a natural way with the fact that threads cannot execute code ‘before’ they have been created but Eraser needs special heuristics to support these kind of unlocked accesses. The support for initialisation makes Eraser dependent on the scheduling order and therefore requires also the checking of all possible executions for each possible input.

The most important problem with Eraser is however that its practical applicability is limited as it can only process mutex synchronisation operations and the tool fails when other synchronisation primitives are built on top of these lock operations.

These problems with Eraser makes us believe that methods based on the happens-before relation (like RecPlay) are better. Contrary to Eraser, it can only detect data races that show up in a particular program run, but it is more general in that it knows how to deal with all common synchronisation operations. Furthermore, it is more reliable because it never reports false data races.

## 6 Conclusions

In this paper, we have presented RecPlay, a practical and effective tool for detecting data races in parallel executions. Therefore, we implemented a highly efficient two-level record/replay system that traces the synchronisation operations, and uses this trace to replay the execution. During replay, a race detection algorithm is run to notify the programmer when a race occurs. As such, synchronisation races are replayed while deta races are detected. Using snooped matrix clocks and multilevel bitmaps, we were able to limit the memory consumption. RecPlay works on running processes, and is therefore completely independent of any compiler or programming language. Moreover, recompiling or relinking the application is not required.

## Acknowledgements

Michiel Ronsse is sponsored by a GOA project (12050895) from Ghent University. Koen De Bosschere is a research associate with the Fund for Scientific Research – Flanders.


format: text

text:
# KNO scaling 30 years later

## 1 THE EARLY YEARS

### 1.1 Polyakov and Koba-Nielsen-Olesen

In the Millennium Year we celebrated the 30th anniversary of the famous Eq. (1), the basic result of Polyakov and of Koba, Nielsen and Olesen concerning the asymptotic behavior of the multiplicity distributions . These authors put forward the hypothesis that at very high energies $`s`$ the probability distributions $`P_n(s)`$ of producing $`n`$ particles in a certain collision process should exhibit the scaling (homogeneity) relation

$$P_n(s)=\frac{1}{n(s)}\psi \left(\frac{n}{n(s)}\right)$$
(1)
as $`s\mathrm{}`$ with $`n(s)`$ being the average multiplicity of secondaries at collision energy $`s`$. This so-called KNO scaling hypothesis asserts that if we rescale $`P_n(s)`$ measured at different energies via stretching (shrinking) the vertical (horizontal) axes by $`n(s)`$, these rescaled curves will coincide with each other. That is, the multiplicity distributions become simple rescaled copies of the universal function $`\psi (z)`$ depending only on the scaled multiplicity $`z=n/n(s)`$. In the picturesque terminology of Stanley  the rescaled data points $`P_n(s)`$ measured at different energies $`s`$ collapse onto the unique scaling curve $`\psi (z)`$. After Koba , let me illustrate this schematically:

$`\text{rescaling}`$
The data collapsing behavior is a fundamental property of homogeneous functions. According to Eq. (1), at very high energies the multiplicity distributions $`P_n(s)`$ are homogeneous functions of degree $`1`$ of $`n`$ and $`n(s)`$. Homogeneity rules play a central role in the theory of critical phenomena . Near the critical point of a physical system the thermodynamic functions exhibit homogeneous form which implies the existence of a law of corresponding states: using a suitably chosen scaling transformation it is possible to bring different states of the same system to coincidence and thus to compress many experimental or theoretical results into a compact form. The KNO scaling hypothesis Eq. (1) is just such a law of corresponding states.

In the celebrated paper  Koba, Nielsen and Olesen showed that the validity of Feynman scaling is a sufficient condition for Eq. (1) to hold. It is worth mentioning however that the mathematical rigor of their derivation was criticized by several authors. Moreover, the precise finding of Ref.  was the energy independence of the moments $`C_q=n^q(s)/n(s)^q`$ in the limit $`s\mathrm{}`$. The scaling hypothesis Eq. (1) was formulated with the additional assumption that the moments $`C_q=_0^{\mathrm{}}z^q\psi (z)𝑑z`$ determine uniquely the scaling function $`\psi (z)`$. Polyakov arrived at the asymptotic multiplicity scaling law Eq. (1) two years earlier than Koba, Nielsen and Olesen by formulating a similarity hypothesis for strong interactions in $`e^+e^{}\text{hadrons}`$ annihilation; see later. Somehow this fundamental and elegant work was almost completely ignored in the early 70s and Eq. (1) became known as the KNO scaling hypothesis in the high-energy physics community.

### 1.2 Modifications

The scaling relation Eq. (1) can hold only approximately since multiplicity $`n`$ is a discrete random variable whose stretching or shrinking by a scale factor leaves the probabilities $`P_n`$ unaltered. The proper meaning of Eq. (1) is that with increasing collision energy $`s`$ the discrete multiplicity distributions $`P_n`$ can be approximated with increasing accuracy by a continuous probability density function $`f(x)`$ via $`P_nf(x=n)`$ (KNO prescription) or by $`P_n_{x=n}^{x=n+1}f(x)𝑑x`$ (called KNO-G “scaling”) where, in the most popular modification of the original scaling rule, $`f(x)`$ has the generic Czyżewski-Rybicki form

$$f(x)=\frac{1}{\lambda }\psi \left(\frac{xc}{\lambda }\right)$$
(2)
with scale parameter $`\lambda >0`$ and location parameter $`c`$. Data collapsing behavior is observed if the only $`s`$-dependent parameters of the approximate shape function $`f(x)`$ are $`c`$ and $`\lambda `$, i.e. if $`f(x)`$ depends on collision energy only through a change of location and scale in $`x`$. The variation of $`\lambda `$ with increasing $`s`$ reflects the growth of average multiplicity, whereas the $`s`$-dependence of $`c`$ is usually associated with leading particle effects (so-called AKNO or KNO-$`\alpha `$ scaling). Other physical explanations are also possible, see e.g. the contribution of Marek Płoszajczak on $`\mathrm{\Delta }`$-scaling.

## 2 NEW SCALING PRINCIPLE

Taking into account a possible location change (shift) in multiplicity rarely proved to be sufficient to restore the data collapsing behavior of $`P_n`$ when the original scaling law Eq. (1) is violated at very high energies (hence we use $`c=0`$). Nevertheless, the principle of scale and location change in the shape of multiplicity distributions can be extremely powerful through the following generalization of the KNO scaling rule. Consider that the multiplicity distributions, more precisely the continuous probability densities $`f(x)`$ approximating $`P_n`$ generate $`s`$-dependent shifting and rescaling in Mellin space. The Mellin transform of a probability density $`f(x)`$ is defined by $`\{f(x);q\}=_0^{\mathrm{}}x^{q1}f(x)𝑑x`$ and it provides the $`(q1)`$th moment $`x^{q1}`$. Via the functional relation

$$\{x^rf\left(x^\mu \right);q\}=\frac{1}{\mu }\{f(x);\frac{q+r}{\mu }\}$$
(3)
one can introduce translation and dilatation in the moments’ rank $`q`$ by performing the transformation $`f(x)x^rf\left(x^\mu \right)`$ of the probability densities approximating the shape of $`P_n`$. In the followings I shall illustrate the utility of performing a location or scale change in Mellin space; for further details, see Refs. .

## 3 TRANSLATION IN M-SPACE

### 3.1 Motivation

There are several possible dynamical explanations of a shift in Mellin space. The basic idea is simply the following. Recall that in Eq. (1) the normalization of the KNO function reads $`_0^{\mathrm{}}\psi (z)𝑑z=_0^{\mathrm{}}z\psi (z)𝑑z=1,`$ that is, $`z=1`$. Assume that violation of KNO scaling is observed and we measure $`s`$-dependent “scaling” functions $`\psi (z)`$. In order to arrive at data collapsing behavior of $`P_n`$ the simplest possibility is to rescale the function $`\phi (z)=z\psi (z)`$ by its first moment given by $`C_2`$. In terms of $`P_n`$ and the moments $`n^q`$ this corresponds to rescaling the distribution $`P_{n,1}=nP_n/n`$ by its mean $`n_1=n^2/n`$. The distribution $`P_{n,1}`$ is known in the mathematical literature as the first moment distribution of $`P_n`$. If the rescaling of $`P_{n,1}`$ by $`n_1`$ is not sufficient to arrive at data collapsing behavior, one can try the same recipe for the higher-order moment distributions $`P_{n,r}=n^rP_n/n^r`$. The generalization is straightforward. Let me show you now an example when Eq. (1) is clearly violated, but performing a shift in Mellin space can restore the collapse of different $`P_n`$ curves onto a single scaling curve.

### 3.2 Intermittency and multifractality

The most obvious example is intermittency. As it turned out during the past 15 years, multiparticle production often yields scale-invariant density fluctuations . This can be observed through the power-law scaling $`C_q\delta ^{\phi _q}`$ of the normalized moments $`C_q=n^q/n^q`$ of $`P_n(\delta )`$ as the bin-size $`\delta `$ in phase-space is varied (for clarity, we neglect here the influence of low count rates). Assuming that the fluctuations show monofractal structure, the so-called intermittency exponents $`\phi _q`$ are given by $`\phi _q=\phi _2(q1)`$ and the anomalous fractal dimensions $`D_q=\phi _q/(q1)`$ are $`q`$-independent, $`D_q=D_2`$. The normalized moments $`C_q`$ of $`P_n(\delta )`$ take the form

$$C_q=A_q[C_2]^{q1}\text{for}q>2$$
(4)
with coefficients $`A_q`$ independent of bin-size $`\delta `$ . Of course Eq. (1), with $`s\delta `$, is violated since we observe $`C_2\delta ^{\phi _2}`$.

In the restoration of data collapsing behavior of $`P_n`$ for self-similar fluctuations the basic trick is the investigation of the higher-order moment distributions defined before. Their moments are $`n^q_r=n^{q+r}/n^r`$, that is, the moments of the original $`P_n`$ are transformed out up to $`r`$th order via performing a shift in Mellin space, see Eq. (3). For $`r=1`$ the normalized moments of the first moment distribution $`P_{n,1}`$ are found to be $`C_{q,1}=C_{q+1}/[C_2]^q`$ in terms of the original $`C_q`$ and comparison to Eq. (4) yields $`C_{q,1}=A_{q+1}`$ for monofractal multiplicity fluctuations. Since the coefficients $`A_q`$ are independent of bin-size $`\delta `$, we see that monofractality yields not only power-law scaling of the normalized moments of $`P_n`$ but also data collapsing behavior of the first moment distributions $`P_{n,1}`$ measured at different resolution scales $`\delta `$. Increasing the (possibly fractional) rank $`r`$ of the moment distributions allows the restoration of data collapsing behavior in the presence of increasing degree of multifractality of scale-invariant multiplicity fluctuations . The effect of low multiplicities (Poisson noise) can be taken into account via the study of factorial moment distributions $`P_{n,r}=n^{[r]}P_n/n^{[r]}`$ and their factorial moments.

### 3.3 Ginzburg-Landau phase transition

In recent years considerable interest has been devoted to the Ginzburg-Landau theory of the phase transition from quark-gluon plasma to hadronic matter . Instead of a strict power-law scaling $`F_q\delta ^{\phi _q}`$ of the normalized factorial moments, a so-called $`F`$-scaling behavior $`F_q[F_2]^{\beta _q}`$ is obtained with $`\beta _q=(q1)^\nu `$. For second-order transition $`\nu =1.304`$ and in case of a first-order transition $`\nu =1.45`$. The $`F`$-scaling rule of the above form makes difficult to identify the family of probability laws $`P_n`$ belonging to the model. But considering $`P_{n,1}`$ instead of $`P_n`$ the corresponding factorial moments turn out to be $`F_{q,1}[F_2]^{\beta _q}`$ with $`\beta _q=q^\nu q`$ and hence

$$F_{q,1}[F_{2,1}]^{\beta _q}\text{with}\beta _q=\frac{q^\nu q}{2^\nu 2}.$$

This form of $`F`$-scaling is the familiar log-Lévy law  with stability index $`0<\nu 2`$. Thus, via moment shifting, we succeeded in identifying $`P_{n,1}`$ for the Ginzburg-Landau formalism with a strict bound on the essential parameter $`\nu `$ of the model. The theoretically relevant values are within the allowed range. Although this particular example is not related directly to data collapsing behavior of multiplicity distributions, it illustrates the utility of the moment distributions $`P_{n,r}n^rP_n`$ which correspond to translation in Mellin space.

## 4 RESCALING IN M-SPACE

### 4.1 Motivation

The most important reason of a possible change of scale in Mellin space comes from QCD. In higher-order pQCD calculations, allowing a more precise account of energy conservation in the course of multiple parton splittings, the natural variable of the multiplicity moments is the rescaled rank $`q\gamma `$ instead of rank $`q`$ itself  with $`\gamma (\alpha _s)`$ being the multiplicity anomalous dimension of QCD. Because of the running of the strong coupling constant $`\alpha _s`$, it is inevitable to adjust an energy dependent scale factor in Mellin space if one wants to arrive at data collapsing behavior of the multiplicity distributions $`P_n(s)`$.

### 4.2 Running coupling

In the very first paper predicting the multiplicity scaling law Eq. (1), Polyakov constructed a model for the short-distance behavior of strong interactions based on the hypothesis of asymptotic scale- and conformal invariance . When applied to the process of $`e^+e^{}`$ annihilation to hadrons at asymptotically high collision energies, the model predicts that multihadron production goes in a cascade way. First, a few heavy virtual objects, called jets, are formed. These are repeatedly diminished in a branching process until the masses of the subsequent generation jets become at some very late stage comparable to the hadronic masses. This cascading mechanism gives rise to multiplicity distributions $`P_n(s)`$ satisfying Eq. (1) and the scaling function $`\psi (z)`$ behaves as $`\psi (z)a(z)\mathrm{exp}(z^\mu )`$ with $`\mu >1`$ and $`a(z)`$ being a monomial. Up to a scale factor, $`\psi (z)`$ is a negative binomial type scaling function, that is, a gamma distribution  in the rescaled and power-transformed multiplicity $`z^\mu `$.

It is worth emphasizing that the above result was achieved years earlier than the emergence of quantum chromodynamics. Interestingly, the predictions of QCD obey some important similarities to the findings of Polyakov:

1) Hadronic jets produced in hard processes are expected in QCD to be self-similar objects composed of subsequent parton branching decays . A highly virtual quark or gluon decays into secondaries which are less off-shell and less energetic. Each of these intermediate decay products splits into novel ones. The subsequent decay chain steps form a scale-invariant branching process which continues until the virtual mass of the quanta becomes approximately 1 GeV.

2) The fragmentation of partons in QCD leads to the typical characteristics of branching processes, in particular, to long-range correlations and to the validity of KNO scaling . Further, it was shown  that KNO scaling in $`e^+e^{}`$ annihilation is the consequence of the scale-invariance (asymptotic freedom) in the presence of gluon self-coupling. It is thus the manifestation of the essence of the non-abelian gauge theory of strong interactions.

3) Taking into account the higher pQCD effects responsible for energy-momentum conservation in parton jets, the KNO scaling function in $`e^+e^{}`$ annihilation was shown  to be identical to Polyakov’s form:

$$\psi (z)=𝒩z^{\mu k1}\mathrm{exp}\left([Dz]^\mu \right)$$
(5)
where $`k=3/2`$, $`𝒩=\mu D^{\mu k}/\mathrm{\Gamma }(k)`$, $`\mu =(1\gamma )^15/3`$ and $`D`$ is a scale parameter depending on $`\gamma `$, with $`\gamma `$ being the QCD anomalous dimension, $`\gamma 0.4`$ at LEP1. Hence, the conservation laws strongly reduce the width of the KNO scaling function as compared to the exponential fall-off obtained by lower-order pQCD calculations. The experimental data at $`\sqrt{s}=91.2`$ GeV (dots) confirm the prediction (curve) as illustrated in the figure a) below (with the exception that $`k`$ turns out to be larger, $`k5`$).

The crucial difference between the QCD prediction and Polyakov’s result lies in the fact that the scaling function $`\psi (z)`$ given by the Polyakov-Dokshitzer form Eq. (5) depends on collision energy $`s`$ in QCD. That is, QCD predicts violation of KNO scaling in $`e^+e^{}`$ annihilation which becomes clearly visible at higher energies. This effect is due to the running of the strong coupling constant $`\alpha _s`$, hence $`\gamma 0`$ as $`s\mathrm{}`$, i.e., $`\mu 1`$ asymptotically . Therefore the tail of $`\psi (z)`$ widens with increasing $`s`$ which gives rise to the KNO scaling violation pattern shown in the figure b) below. Asymptotically the exponential fall-off predicted by the double logarithmic approximation is recovered (solid curve) i.e. the negative binomial type scaling form of $`P_n(s)`$.

Thus we have learned that the pre-QCD and QCD-based descriptions of $`e^+e^{}`$ annihilation to hadrons make essential use of self-similar branching processes, further, both predict the rescaled and power-transformed multiplicity variable $`z^\mu `$ to be gamma-distributed. But in the pre-QCD approach the exponent $`\mu `$ is independent of collision energy $`s`$ and KNO scaling holds valid, as expected for scale-invariant branching with fixed coupling. On the contrary, the QCD-based calculations predict violation of KNO scaling since $`\mu `$ varies with collision energy $`s`$, due to the running of $`\alpha _s`$. Note however that in the latter case data collapsing can be restored in a simple way using logarithmic scaling variable. For the Polyakov-Dokshitzer form of $`\psi (z)`$ given by (5) we have

$$\psi (x)=\mu \mathrm{exp}\left(k\mu xe^{\mu x}\right)/\mathrm{\Gamma }(k),x=\mathrm{ln}(Dz).$$

Since only the exponent $`\mu `$ and scale parameter $`D`$ of Eq. (5) are expected to depend on collision energy $`s`$ through the variation of $`\gamma (\alpha _s)`$, KNO scaling violated by QCD effects is recovered by plotting $`\mu ^1\psi (\mu x)`$ as displayed in the figure c). The scale change in logarithmic multiplicity is governed by the QCD multiplicity anomalous dimension. This particular type of data collapsing of the multiplicity distributions $`P_n(s)`$ is called log-KNO scaling  since we have the behavior of type Eq. (2) except that distributions of the logarithmic multiplicity satisfy it.

### 4.3 Multiplicative cascades

It may turn out that the log-KNO scaling law has ubiquitous appearance in multiparticle dynamics. Random multiplicative cascades play a distinguished role in the dynamics underlying multihadron production, both in soft and hard processes. The multiplicative cascade models like for example the $`\alpha `$-model and $`p`$-model are in the focus of interest since the pioneering work of Białas and Peschanski , see also  for a review. Recently, Frisch and Sornette developed a theory of extreme deviations  which predicts for multiplication of random variables the generic presence of stretched exponential distributions $`f(x)\mathrm{exp}(\lambda x^\mu )`$ with $`\mu <1`$. To be specific, consider the product $`X_N=m_1m_2\mathrm{}m_N`$ of independent random variables $`m_i`$ distributed identically according to the probability density $`p(m_i)`$. The above product can arise in a cascade process if primary entities (e.g. particle density) of initial size $`s_0`$ are repeatedly diminished in random proportions, so that after $`N`$ cascade steps we have the product $`s_N=s_0m_1m_2\mathrm{}m_N`$.

In ref.  it is shown that under mild regularity conditions the distribution of the product variable $`X_N`$ exhibits the asymptotic behavior

$$𝒫_N(X)\left[p\left(X^{1/N}\right)\right]^N\text{for}X\mathrm{}$$
(6)
and for finite $`N`$. Frisch and Sornette call attention to the intuitive interpretation of (6): the tail of $`𝒫_N(X)`$ is controlled by the realizations where all terms in the product are of the same order hence $`𝒫_N(X)`$ is, to leading order, just the product of the $`N`$ densities $`p`$, each having the common argument $`X^{1/N}`$. When $`p(x)`$ is chosen to be $`\mathrm{exp}(\lambda x^\alpha )`$ with $`\alpha >0`$, then Eq. (6) leads to stretched exponential tails $`\mathrm{exp}(\lambda Nx^{\alpha /N})`$ for large $`N`$, with stretching exponent $`\alpha /N<1`$. Expecting the cascade depth $`N`$ to be an increasing function of collision energy $`s`$, Eq. (1) breaks down but data collapsing can be recovered in the log-KNO manner discussed previously.

## 5 SCALING AT TEV ENERGIES

The most exciting and challenging task in developing novel scaling relations is testing them on real data. In case of multiplicity distributions the KNO scaling laws Eqs. (1-2) are known to be strongly violated above ISR energies. This violation is most visible for the multiplicity data measured by the E735 Collaboration  see also  for more details. In the followings I provide a very brief summary of some preliminary results of a study of the E735 data.

### 5.1 Analysis of E735 multiplicities

The E735 Collaboration recently published the full phase-space multiplicity distributions in $`pp`$ and $`p\overline{p}`$ collisions at c.m. energies $`\sqrt{s}=`$ 300, 546, 1000 and 1800 GeV at Tevatron . The $`P_n`$ curves corresponding to $`\sqrt{s}=`$ 300 and 1800 GeV are displayed in the following two figures.

It is apparent that bimodal shape of the $`P_n`$ curves arises at TeV energies, obeying a (not too pronounced) shoulder structure like at SPS. It is argued  that the low-multiplicity regimes are affected mainly by single parton collisions and exhibit KNO scaling, whereas the large-$`n`$ tail of the distributions is influenced more heavily by double parton interactions and violate KNO scaling substantially. Another possible explanation of the observed $`P_n`$ shape is the weighted superposition of a soft and semihard component, the latter one being dominated by minijet production. These components are responsible of the KNO scaling and KNO-violating regimes of $`P_n`$ .

The solid curves in the previous two plots represent the Polyakov-Dokshitzer parametrization Eq. (5) fitted to the KNO-violating $`z1`$ component of the E735 data. The quality of fits is reasonably good (for all data sets) as can be depicted from the figures. The fits correspond to $`k=\frac{1}{2}`$ kept fixed and $`\mu `$ decreasing from $`\mu 2.2`$ to $`\mu 1.7`$ as one goes from $`\sqrt{s}=`$ 300 GeV to 1800 GeV. Our findings indicate that the KNO violating component of the E735 multiplicity distributions can be collapsed onto a single scaling curve in the log-KNO manner discussed previously. It is illustrated below.

In the upper figure the $`\sqrt{s}=`$ 300 and 1800 GeV data sets are displayed only, whereas in the lower plot all the four data sets measured by the E735 experiment. The collapse of the data points onto a unique scaling curve is apparent. This very preliminary investigation suggests that the pattern of KNO scaling violation by double parton collisions, or by semihard processes dominated by minijet production, is similar to that of $`e^+e^{}`$ annihilations where log-KNO behavior is expected to arise as well at high energies (see before). But note that in parameter $`k`$ there is an order of magnitude difference between $`e^+e^{}`$ and $`p\overline{p}`$ collisions, that is, the scaling functions have different shapes in the two reactions.

One of the earliest reviews  of Polyakov’s pioneering work concluded with the following speculative note: “Could it be that as in the theory of critical phenomena, while the basic physics (Hamiltonians) between $`e^+e^{}`$ annihilation and hadronic multiparticle production could be entirely different, multiplicity scaling may yet still be a universal feature shared by both?” In the light of our findings the answer to this question is yes but the scaling behavior foreseen 30 years ago arises in the logarithm of multiplicity instead of multiplicity itself.

## 6 SUMMARY

In the past 30 years, data collapsing of multiplicity distributions $`P_n`$ according to the generic KNO scaling relation Eq. (2) was one of the most extensively studied topics in soft physics. Unfortunately, more and more experimental and theoretical results confirm that Eq. (2) is too simple to be true. The information content of $`P_n`$ can be represented in an equally convenient manner making use of the multiplicity moments. For example, validity of Eq. (2) corresponds to constancy of the normalized central moments for appropriately chosen $`c`$ and $`\lambda `$. What can we do if the KNO scaling rule (2) breaks down? How data collapsing behavior of $`P_n`$ can be restored, if it is possible at all? The approach presented here is extremely simple: let’s perform the original scaling transformation (shifting and rescaling) in the multiplicity moments’ rank, that is, in Mellin space, rather than in multiplicity.

The functional relation Eq. (3) tells how things transform at the level of $`P_n`$. Translation in Mellin space (moment shifting) corresponds to changing from $`P_n`$ to the moment distributions $`P_{n,r}n^rP_n`$. This makes possible to arrive at data collapsing for intermittency phenomena: e.g. $`P_{n,1}`$ scales for monofractal fluctuations, $`P_{n,2}`$ for bifractals and so on. Dilatation in Mellin space (rescaling of moments’ rank) corresponds to the transformation $`P_nP_m`$ with $`m=n^\mu `$. Therefore data collapsing arises in rescaled logarithmic multiplicity (log-KNO). Such behavior is expected to occur for phenomena governed by running coupling effects or in multiplicative cascades of varying length. Considering the physical significance of the mentioned examples in multiparticle dynamics, it will be interesting to see how the proposed scaling behaviors show up in the experiments of the Third Millennium.

## ACKNOWLEDGEMENTS

I am grateful to the organizers of this workshop, in particular to Alberto and Roberto for the invitation and kind hospitality in Torino.

The support of grants NWO-OTKA N25186 and OTKA T024094 is acknowledged.


text:
# Optimising background-limited observing during bright-moon phases and twilight

## 1 Introduction

To make effective use of bright time, ground-based optical telescopes are generally used to observe either sufficiently bright objects in the optical ($`V18`$ mag arcsec-2) or to observe in the near infrared. In the first case, this is to avoid being background limited by the moonlit sky, and in the second case, the sky background is dominated by OH line emission111Note that if the spectral resolution is high enough to observe between the OH lines in the 1–2.2 $`\mu `$m wavelength range, then background continuum becomes important and dark time conditions may then be preferable. or thermal emission from the sky and telescope. For many telescopes, the observatory budget does not extend to expensive high-resolution optical spectrographs or infrared instruments which are suitable for bright-time observations. Some of these telescopes have formed consortia which span the globe to undertake monitoring of variable sources (e.g., pulsating stars, microlensing events, asteroids).

In this paper, we look at strategies for observing during bright time that allow background-limited objects to be observed with higher efficiency. We also look at the possibility of improving observations during twilight. In the optical, the moonlit sky is generally darker along sight lines at large angles from the moon. Additionally, when the moon is near ninety degrees away, the scattered moonlight is highly polarised. By using a polarising filter oriented at the correct angle, the sky background can then be reduced to near-dark or grey conditions.

The degree of polarisation can be defined as

$$P=\frac{I_p}{I_p+I_u}\mathrm{or}\frac{I_1I_2}{I_1+I_2},$$
(1)
where: $`I_p`$ is the polarised intensity and $`I_u`$ is the unpolarised intensity, or; $`I_1`$ is the maximum intensity as measured in one plane of polarisation and $`I_2`$ is the intensity in the orthogonal plane. Studies of the polarisation of twilight (e.g., Coulson 1980, Wu & Lu 1988) have shown that scattered sunlight at ninety degrees has a degree of polarisation of about 0.85. Moonlight scattered at ninety degrees could have a slightly higher degree of polarisation since the light is partially polarised on reflection from the moon (e.g., Dollfus 1962).

The next section quantifies observing efficiency for Poisson-noise limited observations, and determines the gain factor when using a polariser. Sections 3 and 4 discuss observations in moonlight and twilight with and without a polariser.

## 2 Observing efficiency

A figure of merit (proportional to observing efficiency), for a particular instrument observing an object of a certain flux, can be defined as the signal-to-noise ratio squared ($`R^2`$) divided by the integration time ($`t`$). Ignoring read-out noise, this is given by222Equations 2 and 3 relate to observations where the background can be estimated over many more pixels than the object, otherwise the background is effectively higher (e.g., a factor of two in the case of beam switching with fibres).

$$f=\frac{R^2}{t}\frac{ϵO^2}{O+B_d+B_m},$$
(2)
where $`ϵ`$ is the efficiency of the telescope and instrument, $`O`$ is the object flux on the primary mirror, $`B_d`$ is the background flux due to the dark sky (could also include dark current) and $`B_m`$ is the extra background flux due to moonlight and/or twilight (i.e., $`B_m=0`$ for dark-time observations).

Assuming the object and dark-sky fluxes are unpolarised and a polariser is placed in the beam to minimise the extra background flux, the figure of merit is then given by

$$f^{}\frac{\tau ϵ^{}O^2}{O+B_d+(1P_m)B_m+2\gamma P_mB_m},$$
(3)
where $`\tau `$ is the transmission of the polariser with unpolarised light ($`\tau 0.50`$), $`ϵ^{}`$ is the efficiency of the telescope and instrument with polarised light, $`\gamma `$ is the extinction333We define the extinction of a polariser as the ratio of the minimum and maximum transmissions of polarised light, obtained by rotation. of the polariser ($`\gamma 1`$) and $`P_m`$ is the degree of polarisation of the extra light.

The gain in observing efficiency from using a polariser can be written as

$$\frac{f^{}}{f}\tau \frac{ϵ^{}}{ϵ}\left[\frac{O+B_d+B_m}{O+B_d+(1P_m+2\gamma P_m)B_m}\right].$$
(4)
There may also be an extra gain factor due to an improved duty cycle because the background level is lower and, therefore, integration times can be increased. In most cases, $`ϵ^{}/ϵ`$ will be approximately unity444Some existing spectrographs will have a significantly higher throughput in one polarisation state. We also note the possibility of designing a spectrograph to be optimised for one polarisation. For example, this is possible using volume phase holographic gratings. and $`\tau `$ will be in the range 0.35–0.48 (Sec. 2.1). The degree of polarisation could be about 0.90 for moonlight scattered from the sky ninety degrees away from the moon. The extinction should not be a limiting factor with $`\gamma `$ in the range $`10^3`$$`10^2`$.

Setting $`\gamma =0`$, $`ϵ^{}/ϵ=1`$ and rearranging Equation 4, we obtain a condition for gains of greater than or approximately unity ($`f^{}/f1`$):

$$(P_m+\tau 1)B_m(1\tau )(O+B_d).$$
(5)
This condition can also be written as

$$(P+\tau 1)B(1\tau )O,$$
(6)
where $`P`$ is the degree of polarisation of the total background flux ($`B`$). In other words, $`P>1\tau `$ and the background flux must be high enough for a polariser to improve observing efficiency. For example, with $`P=0.78`$ and $`\tau =0.48`$, the background flux must be greater than or approximately twice the object flux.

### 2.1 Polarising filters

Normal polarising filters are notoriously lossy with typical transmissions of 0.70 (one polarisation state). However, thin film polarisers made by ‘bleaching’ can have transmissions as high as 0.96 (Gunning & Foschaar 1983). Here, a polymerising sheet is placed in acetone to eat away most of the plastic. The polarising film is then stretched and deposited over a substrate in a humid oven. Much of the art of bleaching resides in technical reports of the Lockheed Palar Alto Research Laboratory where it was first developed by H. E. Ramsey. When achieving the highest transmissions through bleaching, it is important that the extinction ratio be kept to about 10-2 or lower.

## 3 Observing moonlit sky

To consider the effect of observing objects during moonlit sky, we used the model of moonlight brightness described by Krisciunas & Schaefer (1991). For various moon phases ($`\alpha `$)555The phase $`\alpha `$ is defined as the angular distance between the Earth and the Sun as seen from the Moon., zenith angles and moon-object separation angles, we calculated the observing efficiency (using Equations 2 and 3) relative to dark-time observations at zenith. The extinction of object flux was considered in addition to the variation in background flux. Figure 1 shows the results of these calculations for observations of $`V=22`$ mag arcsec-2 objects during phases from full moon to half moon.

During moonlit bright time ($`|\alpha |<60\mathrm{°}`$), it is generally more efficient to observe with a polariser than without (on appropriate targets, i.e., background limited and near 90° separation from the moon). Remembering that Poisson-noise gains of less than but near unity (Eqn. 4) can provide better observing efficiency if the duty cycle is significantly improved. Additionally, residuals associated with continuum-sky subtraction may be reduced since the relative contribution of the moonlight (solar spectrum) to the overall flux is lower.

During moonlit grey time ($`60\mathrm{°}<|\alpha |<120\mathrm{°}`$), it is generally best to observe without a polariser on targets that are about 40° to 90° away from the moon.

Figure 2 shows the observing efficiency for various object brightnesses about one day away from full moon (relative to dark-time observations of the same object brightness). There is some improvement when using a polariser for objects fainter than about 20 mag arcsec-2 at this moon phase. The brightness for which it is useful to use a polariser depends on the moonlight, the degree of polarisation, the dark-sky contribution, transmission and instrument efficiencies (see Equation 5).

## 4 Observing twilight sky

To consider observations during twilight, we produced a model of the twilight brightness based on the work by Tyson & Gal (1993). The sky brightness versus the elevation angle of the Sun is shown in Figure 3. At sunset, the brightness was assumed to be about 4.5 mag arcsec-2 decreasing towards the dark-sky brightness at the end of astronomical twilight, where we assumed that the twilight contribution was 0.1 times the dark-sky contribution. The flux for the minimum-intensity plane of polarisation, observing about 90° from the Sun, is also shown.

Figure 4 shows the Poisson-noise observing efficiencies for two different brightness objects during twilight. There is only a small range in elevation ($`2\mathrm{°}`$) where the efficiency is above 0.2 with a polariser and where the gain is about or above unity (Eqn. 4). Therefore, there is probably little use for this type of technique during twilight, with the possible exception of observing at high latitude sites, e.g., on the Antarctic continent where polarisers could allow observing in much brighter conditions which can last days or weeks. There, they could be used for site testing even if there are no specific science cases for twilight observing. By extension, a polariser could be used for daytime observations (at any latitude) such as astrometric star or planet measurements (e.g., Rafferty & Loader 1993).

## 5 Discussion

For effective use of a polariser to minimise the sky background, it is necessary to be able to rotate the polariser or the instrument in a short time relative to exposure times. A minor adaption to instruments that are in operation or under design is required, including software to calculate the required rotation angle from the moon and object celestial coordinates. To check the validity of the setup, the sky flux can be measured at various rotation angles (of the polariser or instrument) in order to determine the angle that transmits the minimum sky flux.

For observatories that aim to optimise the use of bright-grey time for background limited observations, observing proposals and telescope schedules need to consider the moon’s position.

Potentially, the most efficient use of bright-time observing with or without a polariser will be for those instruments where $`ϵ^{}/ϵ`$ can be significantly greater than unity. Equation 4 refers to the gain relative to the average of $`f`$ over instrument rotation angles. The ability to rotate the instrument independently of the polariser gives the option to maximise $`ϵ^{}/ϵ`$ or, gains can be made without a polariser just by rotating the instrument so that the background flux is minimised. The factor $`ϵ^{}/ϵ`$ could be measured for existing spectrographs, and in the future, spectrographs could be optimised for one polarisation state.

Under design at the AAO is a tunable Lyot filter that is phase free over a wide field (Bland-Hawthorn et al. 2000). The Lyot filter requires a single polarisation input and therefore such an instrument has effectively $`ϵ^{}/ϵ=2`$ at the appropriate polarisation angle, i.e., a polariser is used in any case. Such an instrument could be used during bright-grey time with instrument rotation used to minimise the sky background without loss of object flux.

### 5.1 Further work

To determine more accurately the gain in using a polariser, it is necessary for more measurements to be made. These include measurements of the polarisation of the moonlight contribution to the sky background, as a function of separation angle from the moon and as a function of wavelength. This is not straightforward because the moonlight contribution can not easily be distinguished from the dark-sky contribution. Important questions to answer are: over what range of the sky is it useful to use a polariser, e.g., 80° to 100° from the moon or only 85° to 95°; for which broad-band filters is it useful, e.g., $`BVRIz`$ or just $`V`$; in the $`RIzJH`$ bands, how is narrower-band imaging or spectroscopy between the OH emission lines affected; how does the degree of polarisation vary with atmospheric conditions?

## 6 Conclusions

We suggest there is a key role to play for telescopes that do not have traditional bright-time instruments. Near all-year-round dark-grey conditions can be obtained for survey work (albeit sometimes at lower efficiency), by consideration of the moon’s position and the use of a polariser during bright time. For any telescope, better use can be made of bright-grey conditions with or without a polariser.

## Acknowledgements

IKB would like to thank Tim Bedding and Hans Kjeldsen, and he hopes that this paper does not result in reduced observing time for stellar oscillation studies.


text:
# The first broad–band X–ray images and spectra of the 30 Doradus region in the LMC Based on observations with XMM–Newton, an ESA Science Mission with instruments and contributions directly funded by ESA Member States and the USA (NASA)

## 1 Introduction

On December 10 1999 the XMM–Newton spacecraft was placed in a 48 hour Earth orbit by the first commercial ARIANE V launcher. XMM–Newton, or X–ray Multi–Mirror Mission (Jansen et al. J (2001)), is the second cornerstone of the Horizon 2000 science program of the European Space Agency ESA.

The EPIC pn camera (Strüder et al. St (2001)) was successfully commissioned during the period of mid January through mid March (Briel et al. Br (2000)). On January 19 2000, shortly after the switch–on of the EPIC pn camera, XMM–Newton received first light on the EPIC pn CCD chip. We selected as first light target a region in the LMC about 10 arcmin southwest of the 30 Doradus~A complex. The field has been known to be very rich in X–ray sources from Einstein (Long et al. L (1981)) and ROSAT observations (Trümper et al. Tr (1991)). There are at least three SNRs (one of those known to contain a pulsar), one OB association and two R associations as well as the SN 1987A. This XMM–Newton first light has already stimulated detailed studies of some of the objects. Here we report some results of the observation with four observation sequences of the same field added totaling an exposure time of 106 ks. The observations are of unprecedented sensitivity, reaching a few 1032 erg/s for point sources. We present and discuss the spectroscopic results over the broadest X–ray bandpass of 0.3 – 12 keV ever covered by a single imaging X-ray instrument for the entire field of 27$`\times `$27 arcmin2. In section 2 we describe details of the data analysis techniques which may be useful for other observations as well. In section 3 we discuss some of the scientific results.

## 2 Observations and Data Reduction

The region in the LMC was observed with the pn CCD camera operating in full frame mode (frame time: 73 ms), with the medium and thin filter inserted during the first three and last two observations, respectively (Strüder et al. St (2001) and Turner et al. Tu (2001)). In Tab. 1 we show the journal of the observations. For a fixed pointing direction some photons fall onto the gaps between adjacent CCD chips. Fortunately, the pointing direction and the roll angle were changed for the later three observations with about the same exposure time as for the previous two observations, such that the surface brightnesses are within a factor of 2, with any noise contribution negligible. The data analysis was performed with software which was developed for the analysis of ground calibration measurements of the EPIC pn camera (Dennerl et al. De (1999)). Most of this software has been implemented into the XMM Standard Analysis Software (SAS, Watson et al. Wat (2001)).

During the observations the background induced by low energy protons changed and reached sometimes count rates of several hundred counts per second in the full energy band. To enhance the signal to noise ratio, we screened the observations for times with high background and excluded those times from further processing. The net observing time after screening is 54.8 ks. In addition the trails of minimum ionizing particles and reemission trails were removed frame by frame. The remaining events were corrected for charge transfer loss and gain variations, and events created by a single photon, but split across several pixels, were recombined, to yield a photon event file in detector coordinates with corrected energies (see Dennerl et al. De (1999) for a detailed description).

Test images produced from this data set in various energy bands indicated that the energy range $`E=0.35.0\text{ keV}`$ was optimal to provide clean images with high signal to noise ratio. The energy range was then split into three narrower bands of similar signal to noise ratio, to create red, green and blue components of the final rgb image. The variation in spectral hardness of the LMC sources and the spectral resolution of the EPIC pn camera resulted in colourful images which, however, do not represent the dynamic range in intensity very well. To preserve the flux information as well, the colour saturation was reduced by choosing overlapping energy ranges (0.3 – 1.0 keV for red, 0.8 – 2.0 keV for green, and 1.5 – 5.0 keV for blue), and by further distributing some of the flux from these bands into other bands.

True images of the sky were obtained by projection of each photon onto the celestial plane, taking into account the different pointing directions and roll angles. The projection takes care of the different spacing between the individual CCDs as well as for the larger size of the pixels which are furthest away from the readout nodes (Strüder et al. St (2001)). The result of the projection, after removing events from bright pixels and a bright column, is shown in Fig. 1. The gaps between the CCDs show up in the image, as no exposure correction was applied. The exposure map (Fig. 2) shows that these areas also received some light. The exposure map was created in a similar way as the photon image, using the vignetting curve for 1.5 keV from the XMM Users’ Manual (Dahlem Da (1999)).

Apparent in Fig. 1 is a streak–like feature from the SNR N157B. This is an artefact of the operation of the CCD, which is sensitive to X–rays also during readout. In the full frame mode, 7 % of all events are recorded during this period and get a displaced position along readout direction. This effect occurs everywhere on the detector, but out–of–time event trails are evident only for bright sources. Suppressing the trails does not only improve the image cosmetically, but also reduces local variations of the background needed to apply the source detection algorithms. In the following we describe a straightforward method to suppress the contamination by out–of–time events.

As the generation of out–of–time events is a random process, these events become uniformly distributed along each readout channel. The fraction of out–of–time events is given by the ratio of readout vs. frame time. Thus, if $`n`$ is the total number of photons recorded in a particular column, the contamination $`n_{\mathrm{cont}}`$ of any pixel in this column by out–of–time events is

$$n_{\mathrm{cont}}=\frac{t_{\mathrm{read}}}{t_{\mathrm{frame}}n_{\mathrm{pix}}}n$$

where $`t_{\mathrm{read}}`$, $`t_{\mathrm{frame}}`$ and $`n_{\mathrm{pix}}=200`$ are the readout time, the frame time and the number of pixels per column. For the full frame mode, the values are $`t_{\mathrm{read}}=5\text{ ms}`$ and $`t_{\mathrm{frame}}=73\text{ ms}`$. Fig. 3 shows the contamination of Fig. 1 by out–of–time events, calculated separately for the three colour bands in detector coordinates and then projected onto the sky, so that it can be subtracted from Fig. 1.

An additional source of undesired ‘background’ in Fig. 1 are sharp, blue arcs in the lower corner, which would systematically contaminate the spectra of the diffuse soft X–ray emission in this region. These are caused by single mirror reflections of photons from the bright X–ray binary LMC~X–1, which is outside the FOV. In order to suppress these arcs, we identified the contaminated pixels from the hard images, where they are most distinct, and flagged them (Fig. 4). For the first light image, we replaced the flux of the affected pixels by interpolated values from the adjacent pixels. This approach seems to be justified, since the extent of one pixel ($`4\stackrel{}{.}13`$) is considerably smaller than the half energy width of the telescope ($`15\stackrel{}{.}1`$), which implies that the fluxes of adjacent pixels cannot be independent of each other due to the point spread function of the telescope.

A final challenge for producing the first light image was the high dynamic range in intensity, which exceeds three orders of magnitude between the diffuse extended regions of low surface brightness and the point source in N157B. Since standard techniques like logarithmic intensity coding did not yield satisfying results, we designed a special code which preserves different shades of gray for the brighest sources. The final image, boxed with an equatorial coordinate grid, is shown in Fig. 5.

## 3 Results and Discussion

As Fig. 5 shows, there is a wealth of different objects, point–like and extended up to 130 pc in size. The X–ray colours show large spectral differences from object to object. Based on this image, we accumulated photons from selected regions and performed spectral investigations of various sources, to utilize the full resolving power of the EPIC pn camera. We did this separately for the three data sets which were taken with the same observational setup (filter and pointing direction), because they require different detector response matrices. The best fit was obtained by modeling each of the three count rate spectra with the same candidate source spectrum but with the individual normalization factor left as a free parameter (for details see Haberl et al. Hab (2001)). Errors were determined at $`\mathrm{\Delta }\chi ^2=+2.3`$ with all parameters free.

### 3.1 30 Dor C

The largest object in the field is 30 Dor C, already known from radio observations and suggested by Mills et al. (Mi (1984)) to be an SNR. In X–rays it appears as a complete ring of $`6`$ arcmin diameter. The size of the shell and its colour make this remnant the first of its kind outside our Galaxy. In a separate paper (Aschenbach et al. 2001a ) this unique object is investigated in detail. Close to the geometric center we detect a previously unknown point source, displayed in yellow, which emits mainly in the 0.3 – 1.0 keV band. If this source is in the LMC, then its luminosity is of the order of $`10^{33}\text{ erg s}^1`$, and it might be the compact remnant of 30 Dor C, either a neutron star or a black hole.

### 3.2 SN 1987A

Approximately 2 arcmin to the south-west of the shell border is the well–known SN 1987A. The XMM–Newton observations are very important with respect to both, the light curve and the X–ray spectrum, refining current models of SN 1987A. Both aspects are presented and discussed in an accompanying paper by Aschenbach et al. (2001b ).

### 3.3 Active Galactic Nuclei behind the LMC

A number of point sources have been discovered, displayed as blue dots in Fig. 5, the brightest of which is seen close to the image center. These sources have power law spectra and show strong low energy absorption. Both, the spectra and the fact that the central source is associated with a radio point source, indicate that we see background sources, probably AGN, Nuclei, through and far beyond the LMC. A detailed analysis of these new X–ray sources is presented in an accompanying paper by Haberl et al. (Hab (2001)).

### 3.4 N157B

By far the brightest object in the field is the SNR N157B, located halfway from the image center to the edge in north–easterly direction. After the discovery of the 16 ms pulsar (Marshall et al. Ma (1998), Wang & Gotthelf 1998b ) N157B has been classified as a Crab–like remnant with a central pulsar and a surrounding synchrotron nebula. In a preceeding paper Wang & Gotthelf (1998a ) showed that the spectrum is dominated by a power law with an indication of some thermal emission. The XMM–Newton spectrum of N157B (Fig. 6) demonstrates convincingly for the first time the presence of emission lines at low energies, proving the presence of a thermal component. A model comprising two thermal components and a power law gives an acceptable fit to the data. Formally, ionization equilibrium models like Raymond–Smith (RS; Raymond & Smith R (1977)) or non equilibrium ionization models (NEI; Hamilton et al. Ham (1983)) of XSPEC used for the thermal components at low energies cannot be discriminated.

Fig. 6 shows the best fit two temperature RS models with a power law model added. The temperatures are 0.37$`{}_{0.05}{}^{}{}_{}{}^{+0.11}`$ keV and 0.12$`\pm 0.01`$ keV, and the photon index of the power law is 2.83$`\pm `$0.03. With an assumed hydrogen equivalent photoelectric absorption of $`610^{20}`$ H–atoms cm-2 for the galactic foreground, we derive an additional H–equivalent column density of (1.94$`\pm `$0.04)$`10^{22}`$ H–atoms cm-2 for the absorption in the LMC, taking elemental abundances of 0.5 solar into account. To fit the Mg emission line at 1.3 keV clearly seen in the spectra, an overabundance of 1.3 solar is required (for the cooler component). The NEI model yields similar values for the absorption, the Mg abundance and the power law slope, but different temperatures (0.24 and 0.10 keV).

The existence of the additional two–temperature thermal component suggests that N157B is not a Crab–like remnant but a composite remnant with an X-ray bright pulsar and synchrotron nebula but relatively faint thermal shell. The analysis of the thermal component, to be done in a separate paper, will be used to check for instance the consistency of the age derived from a Sedov–type approach with the pulsar characteristic spin-down age of $`P/(2\dot{P})5000\text{ ys}`$ (Wang & Gotthelf 1998b ).

The power law component in the spectrum of N157B which has been discovered by Wang & Gotthelf (1998a ) using ROSAT PSPC and ASCA SIS data gives a photon index of 2.3$`\pm `$0.1. The EPIC pn best fit value for the index is 2.83$`\pm `$0.03. N157B has been compared with the Crab. Both the Crab pulsar and the N157B 16~ms pulsar (Marshall et al. Ma (1998)) show a flat power law spectrum with a photon index of 1.5 and 1.6$`\pm `$0.3, respectively. The spectrum of the Crab nebula is steeper by 0.5, generally believed to be due to synchrotron losses. If the spectrum of N157B would have a similar difference of $`0.5`$ between the pulsar and the nebula spectrum as suggested by the analysis of Wang & Gotthelf, the analogy with the Crab would be convincing. If on the other hand the EPIC pn power law slope is a better representation of the spectrum, the analogy with the Crab is cleary violated and other acceleration and loss processes have to be considered. We note that the analysis of power law dominated spectra like in AGN show just minor discrepancies in the spectral index between ASCA and EPIC pn. Because of the steep spectrum of the nebula the physical conditions, either the electron injection spectrum, the electron transport speed or the magnetic field distribution, are likely to be different from those prevailing in the Crab.

### 3.5 The Honeycomb nebula

In Fig. 5, X–ray emission from the Honeycomb nebula is seen 1 arcmin south–east of SN 1987A. The emission of the bright orange patch can be modeled by a thermal plasma with a temperature of 0.19$`\pm `$0.02 keV, superimposed on a power law of index 3.6$`\pm `$0.6. Increased Ne and Mg abundances ($``$2 times solar) are indicated. The hydrogen equivalent LMC absorption to this SNR is (2.2$`\pm `$0.9)$`10^{21}`$ H–atoms cm-2. Fig. 7 shows the three EPIC pn spectra together with the best fit model.

### 3.6 Interstellar medium in the LMC

The north–western part of Fig. 5 appears remarkably dark and empty. But when we extract a spectrum from a 44 arcmin2 region north of 30 Dor C where no point sources and no out–of–time events from 30 Dor C affect the data, we clearly see thermal emission. The temperature appears to differ from place to place over a range from $``$0.1 keV and $``$0.3 keV, as was already concluded from ROSAT PSPC spectra (Sasaki et al. Sa (2001)). But for the first time we detect emission lines of oxygen, neon, magnesium and silicon (Fig. 8). To fit the spectrum, we subtracted the background in a preliminary way, using source free areas from other EPIC pn observations. The resulting spectrum is well represented by a 0.3$`{}_{0.2}{}^{}{}_{}{}^{+0.05}`$ keV RS type model with overabundances in O, Ne, Mg and Si of 1.6$`\pm `$0.7, 5.4$`\pm `$1.5, 6.6$`\pm `$2.5 and 8.9$`\pm `$7.4 solar, respectively, which is surprising in view of the generally low metallicity of the LMC.

###### Acknowledgements.

The XMM–Newton project is supported by the Bundesministerium für Bildung und Forschung / Deutsches Zentrum für Luft- und Raumfahrt (BMFT/DLR), the Max–Planck Society and the Heidenhain–Stiftung.