text:
# Week 4 - Recurrences

## Notes

### Master Theorem

$T(n) = aT(\dfrac{n}{b}) + f(n)$, where $a \geq 1, b > 1$, then

\begin{align*} T(n) = \begin{cases} &\Theta(n^{\lg_b a}) &\text{, where } f(n) = o(n^{\lg_b a}) \\\\ &\Theta(n^{\lg_b a}\lg n) &\text{, where } f(n) = \Theta(n^{\lg_b a}) \\\\ &\Theta(f(n)) &\text{, where } f(n) = \omega(n^{\lg_b a}) \textbf{ and } af(n/b) = O(f(n)) \end{cases} \end{align*}

## Assignment - Due 10/20/2018

Credit: source code of questions are from walkccc.

### 4.3-6

Show that the solution to $T(n) = 2T(\lfloor n / 2 \rfloor + 17) + n$ is $O(n\lg n)$.

Suppose that $T(n) = O(\lg n)$, then $\exists c>0$, letting

\begin{align*} T(n) = &2T(\bigg\lfloor\dfrac{n}{2}\bigg\rfloor+17) + n \leq c(n-34)\lg(n-34)\\ T(n) = &2T(\bigg\lfloor\dfrac{n}{2}\bigg\rfloor+17) + n\\ &\leq 2T(\dfrac{n}{2}+17) + n\\ &\leq 2c(\dfrac{n}{2}+17-34)\log(\dfrac{n}{2}+17-34) + n\\ &= c(n-34)(\lg(n-34) - \lg2) + n\\ &= c(n-34)\lg(n-34) - c(n-34) + n\\ &\leq c(n-34)\lg(n-34)\\ c&\geq \dfrac{n}{n-34} = 35\text{ }(n_0 = 35) \end{align*}

So when $c \geq 35, n_0 = 35$, the inequality holds, which is

T(n) = 2T(\bigg\lfloor\dfrac{n}{2}\bigg\rfloor+17) + n = O(\lg n)

### 4.3-7

Using the master method in Section 4.5, you can show that the solution to the recurrence $T(n) = 4T(n / 3) + n$ is $T(n) = \Theta(n^{\log_3 4})$. Show that a substitution proof with the assumption $T(n) \le cn^{\log_3 4}$ fails. Then show how to subtract off a lower-order term to make the substitution proof work.

If we suppose that $\exists{c>0}$ letting $T(n) = 4T(\dfrac{n}{3}) + n \leq cn^{\log_3{4}}$:

\begin{align*} T(n) &= 4T(\dfrac{n}{3}) + n\\ &\leq 4c\times(\dfrac{n}{3})^{\log_3{4}} + n\\ &= cn^{\log_3{4}} + n\\ &\leq cn^{\log_3{4}} \end{align*}

But this lead to $n \leq 0$, which is impossible, the substitution proof above fails. Instead, if we suppose $\exists{c>0}$, letting $T(n) = 4T(\dfrac{n}{3}) + n \leq cn^{\log_3{4}} - dn$:

\begin{align*} T(n) &= 4T(\dfrac{n}{3}) + n\\ &\leq 4(c\times(\dfrac{n}{3})^{\log_3{4}} - d(\dfrac{n}{3})) + n\\ &= cn^{\log_3{4}} - \dfrac{4d}{3}n + n\\ &\leq cn^{\log_3{4}} - dn\\ d&\geq 3 \end{align*}

So when $c>0, d \geq 3$, the inequality holds, which is

T(n) = 4T(\dfrac{n}{3}) + n = \Theta(n^{\log_3{4}})

### 4.3-8

Using the master method in Section 4.5, you can show that the solution to the recurrence $T(n) = 4T(n / 2) + n^2$ is $T(n) = \Theta(n^2)$. Show that a substitution proof with the assumption $T(n) \le cn^2$ fails. Then show how to subtract off a lower-order term to make the substitution proof work.

If we suppose that $\exists{c>0}$, letting $4T(\dfrac{n}{2}) + n^2 \leq cn^2$:

\begin{align*} T(n) &= 4T(\dfrac{n}{2}) + n^2\\ &\leq 4c\times(\dfrac{n}{2})^2 + n^2\\ &= cn^2 + n^2\\ &\leq cn^2 \end{align*}

In fact, according to Master Theorem, the asymptotic bound of $T(n)$ is $\Theta(n^2\lg n)$. Suppose $\exists c>0, \exists d>0$, letting $4T(\dfrac{n}{2}) + n^2 \leq cn^2\lg n - dn$:

\begin{align*} T(n) &= 4T(\dfrac{n}{2}) + n^2\\ &\leq 4(c\times(\dfrac{n}{2})^2\lg{(\dfrac{n}{2})} - d(\dfrac{n}{2}))+ n^2\\ &= cn^2\lg{n} - cn^2 - 2dn + n^2\\ &\leq cn^2\lg{n} - dn\\ c&\geq 1 \end{align*}

So when $c \geq 1, d > 0, T(n) = O(n^2\lg n)$.

Similarly, we can prove $T(n) = \Omega(n^2\lg n)$. which is

T(n) = 4T(\dfrac{n}{2}) + n^2 = \Theta(n^2\lg n)

### 4.3-9

Solve the recurrence $T(n) = 3T(\sqrt n) + \log n$ by making a change of variables. Your solution should be asymptotically tight. Do not worry about whether values are integral.

Since $T(n) = 3T(\sqrt{n}) + \lg{n}$, let $n = 2^k$, then

T(2^k) = 3T(2^\frac{k}{2}) + k

Let $S(k) = T(2^k)$, then

S(k) = 3S(\dfrac{k}{2}) + k

According to Master Theorem, we can suppose

S(k) = \Theta(k^{\lg{3}})

then $\exists c > 0, \exists d > 0, \exists e > 0, \exists f > 0$ letting

ck^{\lg{3}} + dk\leq S(k) \leq ek^{\lg{3}} - fk
\begin{align*} S(k) &= 3S(\dfrac{k}{2}) + k &S(k)&= 3S(\dfrac{k}{2}) + k\\ &\leq 3(e(\dfrac{k}{2})^{\lg{3}}-f\dfrac{k}{2})+k& &\geq 3(c(\dfrac{k}{2})^{\lg{3}}+d\dfrac{k}{2})+k\\ &= ek^{\lg{3}} + \frac{2-3f}{2}k & &= ck^{\lg{3}} + \frac{2+3d}{2}k\\ &\leq ek^{\lg{3}} - fk & &\geq ck^{\lg{3}} + dk\\ f&\geq 2 & d&\geq -2\text{ ($d>0$)} \end{align*}

So, when $c>0, d > 0, e>0, f\geq 2, S(k) = \Theta(k^{\lg3})$, which is

T(n) = S(\lg n) = \Theta(\lg^{\lg3}{n})

### 4.4-1

Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = 3T(\lfloor n / 2 \rfloor) + n$. Use the substitution method to verify your answer.

Suppose $n$ is exact power of 2, we can draw the tree:

• At level $i$, the size is $\dfrac{n}{2^i}$, and the number of nodes is $i$ is $3^i$, so the cost is
3^i \times \dfrac{n}{2^i} = (\dfrac{3}{2})^i{n}
• Specifically, the size at the last level is 1, so the number of levels is $\lg n$, and the cost is:
3^{\lg{n}} \times 1 = n^{\lg{3}} = \Theta{(n^{\lg{3}})}

The total cost of the tree is:

\begin{align*} T(n) &= \sum_{i=0}^{\lg{n}-1} (\dfrac{3}{2})^i{n} + \Theta{(n^{\lg{3}})}\\ &\leq \frac{(\frac{3}{2})^{\lg{n}-1+1}-1}{\frac{3}{2}-1}n + \Theta{(n^{\lg{3}})}\\ &= 2n(\dfrac{3}{2})^{\lg{n}}-1) + \Theta{(n^{\lg{3}})}\\ &= 2n(n^{\lg{\frac{3}{2}}}-1) + \Theta{(n^{\lg{3}})}\\ &= 2(n^{\lg3}-n) + \Theta{(n^{\lg{3}})}\\ &= O(n^{\lg3}) \end{align*}

We use substitution to prove the conclusion above is right. Suppose $T(n) = O(n^{\lg3})$, $\exists c>0, \exists d>0$ letting

\begin{align*} T(n) &= 3T(\bigg\lfloor\dfrac{n}{2}\bigg\rfloor) + n \\ &\leq cn^{\lg3} - dn\\ \\ T(n) &= 3T(\bigg\lfloor\dfrac{n}{2}\bigg\rfloor) + n\\ &\leq 3T(\dfrac{n}{2}) + n\\ &\leq 3c(\dfrac{n}{2})^{\lg3} - \dfrac{3d}{2}n + n\\ &= cn^{\lg3} - \dfrac{3d}{2}n + n\\ &\leq cn^{\lg3} - dn\\ d&\geq 2 \end{align*}

So, when $c>0, d \geq 2$, $T(n) = O(n^{\lg3})$.

### 4.4-2

Use a reccursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = T(n / 2) + n^2$. Use the substitution method to verify your answer.

Suppose $n$ is exact power of 2, we can draw the tree:

• At level $i$, the size is $\dfrac{n}{2^i}$, and the number of nodes is $i$, so the cost is $\dfrac{n^2}{4^i}$.
• Specifically, the size at the last level is 1, so the number of levels is $\lg n$, and the cost is 1. So the total cost of the tree is:
\begin{align*} T(n) &= \sum_{i=0}^{\lg{n}-1} (\dfrac{1}{4})^i{n^2} + 1\\ &\leq \sum_{i=0}^{+\infty} (\dfrac{1}{4})^i{n^2} + 1\\ &= \dfrac{1}{1 - 1/4}n^2 + 1\\ &= O(n^2) \end{align*}

We use substitution to prove the conclusion above is right. Suppose $T(n) = O(n^2)$, $\exists c>0$ letting $T(n) \leq cn^2$:

\begin{align*} T(n) &= T(\dfrac{n}{2}) + n^2\\ &\leq c(\dfrac{n}{2})^2 + n^2\\ &= (1 + \dfrac{c}{4})n^2\\ &\leq cn^2\\ c&\geq \dfrac{4}{3} \end{align*}

Thus the inequality holds, $T(n) = O(n^2)$.

### 4.4-3

Use a reccursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = 4T(n / 2 + 2) + n$. Use the substitution method to verify your answer.

We can make a good guess by looking into $T(n) = 4T(n / 2 + 2) + n$ instead. Suppose $n$ is exact power of 2, we can draw the tree:

• At level $i$, the size is $\dfrac{n}{2^i}$, and the number of nodes is $4^i$, so the cost is $4^i \cdot \dfrac{n}{2^i} = 2^i{n}$.

• Specifically, the size at the last level is 1, so the number of levels is $\lg n$, and it has $n^2$ leaves. The total cost of the tree is:

\begin{align*} T(n) &= \sum_{i=0}^{\lg{n}-1} 2^i{n} + n^2\\ &= \frac{2^{\lg n}-1}{2-1} + n^2\\ &= n^2 + n - 1\\ &= O(n^2) \end{align*}

We use substitution to prove the conclusion above is right. Suppose $T(n) = O(n^2)$, $\exists c>0, \exists d>0$ letting $T(n) \leq cn^2 - dn$:

\begin{align*} T(n) &= 4T(\dfrac{n}{2} + 2) + n\\ &\leq 4(c(\dfrac{n}{2} + 2)^2 - d(\dfrac{n}{2} + 2)) + n\\ &= 4(c(\dfrac{n}{2} + 2)^2 - d(\dfrac{n}{2} + 2)) + n\\ &= cn^2 + (8c-2d+1)n + 16c-8d\\ &\leq cn^2 - dn\\ c&> 0, d \geq 8c + 1 \end{align*}

Thus the inequality holds, $T(n) = O(n^2)$.

### 4.4-4

Use a reccursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = 2T(n - 1) + 1$. Use the substitution method to verify your answer.

We can draw the tree:

• At level $i$, the size is $(n-i)$, and the number of nodes is $2^i$, and the cost is $2^i$.
• Specifically, the size at the last level is 1, so the number of levels is $2^n$. The total cost of the tree is:
\begin{align*} T(n) &= \sum_{i=0}^{n-1} 2^i + 2^n\\ &\leq \sum_{i=0}^{n-1} 2^i + 2^n\\ &= \frac{2^n-1}{2-1} + 2^n\\ &= O(2^n) \end{align*}

We use substitution to prove the conclusion above is right. Suppose $T(n) = O(2^n)$, $\exists c>0, \exists d>0$ letting $T(n) \leq c2^n - d$:

\begin{align*} T(n) &= 2T(n-1) + 1\\ &\leq 2(c2^{n-1} - d) + 1\\ &= c2^n - 2d + 1\\ &\leq c2^n - d\\ c&> 0, d \geq \dfrac{1}{2} \end{align*}

Thus the inequality holds, $T(n) = O(2^n)$.

### 4.4-5

Use a recursion tree to determine a good asymptotic upper bound on the recurrence $T(n) = T(n - 1) + T(n / 2) + n$. Use the substitution method to verify your answer.

This is an unbalance tree, and its scale is between $T(n) = 2T(\dfrac{n}{2}) + n$ and $T(n) = 2T(n-1) + n$. So guess $T(n) = O(2^n)$, $\exists a>0, \exists b>0$ letting $T(n) \leq a2^n-bn$:

\begin{align*} T(n) &= T(n-1) + T(\dfrac{n}{2}) + n\\ &\leq a2^{n-1}-b(n-1) + a2^{\frac{n}{2}}-b\dfrac{n}{2} + n\\ &= a(2^{n-1} + 2^{\frac{n}{2}}) + (1-\dfrac{3}{2}b)n + b\\ &\leq a(2^{n-1} + 2^{n-1}) + (1-\dfrac{3}{2}b)n + b\text{ ($n\geq 2$)}\\ &\leq a2^n-bn\\ a &> 0, b > 2, n_0 = 2 \end{align*}

Thus the inequality holds, $T(n) = O(2^n)$.

### 4.5-1

Use the master method to give tight asymptotic bounds for the following recurrences:

a. $T(n) = 2T(n / 4) + 1$.

b. $T(n) = 2T(n / 4) + \sqrt n$.

c. $T(n) = 2T(n / 4) + n$.

d. $T(n) = 2T(n / 4) + n^2$.

a. $\Theta(n^{\lg_4 2}) = \omega(1) \Rightarrow \Theta(\sqrt{n})$

b. $\Theta(n^{\lg_4 2}) = \Theta(\sqrt{n}) \Rightarrow \Theta(\sqrt{n}\lg n)$

c. $\Theta(n^{\lg_4 2}) = o(n) \Rightarrow \Theta(n)$

d. $\Theta(n^{\lg_4 2}) = o(n^2) \Rightarrow \Theta(n^2)$

format: plain


text:
# Placement Groups¶

## Autoscaling placement groups¶

Placement groups (PGs) are an internal implementation detail of how Ceph distributes data. You can allow the cluster to either make recommendations or automatically tune PGs based on how the cluster is used by enabling pg-autoscaling.

Each pool in the system has a pg_autoscale_mode property that can be set to off, on, or warn.

• off: Disable autoscaling for this pool. It is up to the administrator to choose an appropriate PG number for each pool. Please refer to Choosing the number of Placement Groups for more information.

• on: Enable automated adjustments of the PG count for the given pool.

• warn: Raise health alerts when the PG count should be adjusted

To set the autoscaling mode for existing pools,:

ceph osd pool set <pool-name> pg_autoscale_mode <mode>

For example to enable autoscaling on pool foo,:

ceph osd pool set foo pg_autoscale_mode on

You can also configure the default pg_autoscale_mode that is applied to any pools that are created in the future with:

ceph config set global osd_pool_default_pg_autoscale_mode <mode>

### Viewing PG scaling recommendations¶

You can view each pool, its relative utilization, and any suggested changes to the PG count with this command:

ceph osd pool autoscale-status

Output will be something like:

POOL    SIZE  TARGET SIZE  RATE  RAW CAPACITY   RATIO  TARGET RATIO  EFFECTIVE RATIO PG_NUM  NEW PG_NUM  AUTOSCALE
a     12900M                3.0        82431M  0.4695                                     8         128  warn
c         0                 3.0        82431M  0.0000        0.2000           0.9884      1          64  warn
b         0        953.6M   3.0        82431M  0.0347                                     8              warn

SIZE is the amount of data stored in the pool. TARGET SIZE, if present, is the amount of data the administrator has specified that they expect to eventually be stored in this pool. The system uses the larger of the two values for its calculation.

RATE is the multiplier for the pool that determines how much raw storage capacity is consumed. For example, a 3 replica pool will have a ratio of 3.0, while a k=4,m=2 erasure coded pool will have a ratio of 1.5.

RAW CAPACITY is the total amount of raw storage capacity on the OSDs that are responsible for storing this pool’s (and perhaps other pools’) data. RATIO is the ratio of that total capacity that this pool is consuming (i.e., ratio = size * rate / raw capacity).

TARGET RATIO, if present, is the ratio of storage that the administrator has specified that they expect this pool to consume relative to other pools with target ratios set. If both target size bytes and ratio are specified, the ratio takes precedence.

EFFECTIVE RATIO is the target ratio after adjusting in two ways:

1. subtracting any capacity expected to be used by pools with target size set

2. normalizing the target ratios among pools with target ratio set so they collectively target the rest of the space. For example, 4 pools with target_ratio 1.0 would have an effective ratio of 0.25.

The system uses the larger of the actual ratio and the effective ratio for its calculation.

PG_NUM is the current number of PGs for the pool (or the current number of PGs that the pool is working towards, if a pg_num change is in progress). NEW PG_NUM, if present, is what the system believes the pool’s pg_num should be changed to. It is always a power of 2, and will only be present if the “ideal” value varies from the current value by more than a factor of 3.

The final column, AUTOSCALE, is the pool pg_autoscale_mode, and will be either on, off, or warn.

### Automated scaling¶

Allowing the cluster to automatically scale PGs based on usage is the simplest approach. Ceph will look at the total available storage and target number of PGs for the whole system, look at how much data is stored in each pool, and try to apportion the PGs accordingly. The system is relatively conservative with its approach, only making changes to a pool when the current number of PGs (pg_num) is more than 3 times off from what it thinks it should be.

The target number of PGs per OSD is based on the mon_target_pg_per_osd configurable (default: 100), which can be adjusted with:

ceph config set global mon_target_pg_per_osd 100

The autoscaler analyzes pools and adjusts on a per-subtree basis. Because each pool may map to a different CRUSH rule, and each rule may distribute data across different devices, Ceph will consider utilization of each subtree of the hierarchy independently. For example, a pool that maps to OSDs of class ssd and a pool that maps to OSDs of class hdd will each have optimal PG counts that depend on the number of those respective device types.

### Specifying expected pool size¶

When a cluster or pool is first created, it will consume a small fraction of the total cluster capacity and will appear to the system as if it should only need a small number of placement groups. However, in most cases cluster administrators have a good idea which pools are expected to consume most of the system capacity over time. By providing this information to Ceph, a more appropriate number of PGs can be used from the beginning, preventing subsequent changes in pg_num and the overhead associated with moving data around when those adjustments are made.

The target size of a pool can be specified in two ways: either in terms of the absolute size of the pool (i.e., bytes), or as a weight relative to other pools with a target_size_ratio set.

For example,:

ceph osd pool set mypool target_size_bytes 100T

will tell the system that mypool is expected to consume 100 TiB of space. Alternatively,:

ceph osd pool set mypool target_size_ratio 1.0

will tell the system that mypool is expected to consume 1.0 relative to the other pools with target_size_ratio set. If mypool is the only pool in the cluster, this means an expected use of 100% of the total capacity. If there is a second pool with target_size_ratio 1.0, both pools would expect to use 50% of the cluster capacity.

You can also set the target size of a pool at creation time with the optional --target-size-bytes <bytes> or --target-size-ratio <ratio> arguments to the ceph osd pool create command.

Note that if impossible target size values are specified (for example, a capacity larger than the total cluster) then a health warning (POOL_TARGET_SIZE_BYTES_OVERCOMMITTED) will be raised.

If both target_size_ratio and target_size_bytes are specified for a pool, only the ratio will be considered, and a health warning (POOL_HAS_TARGET_SIZE_BYTES_AND_RATIO) will be issued.

### Specifying bounds on a pool’s PGs¶

It is also possible to specify a minimum number of PGs for a pool. This is useful for establishing a lower bound on the amount of parallelism client will see when doing IO, even when a pool is mostly empty. Setting the lower bound prevents Ceph from reducing (or recommending you reduce) the PG number below the configured number.

You can set the minimum number of PGs for a pool with:

ceph osd pool set <pool-name> pg_num_min <num>

You can also specify the minimum PG count at pool creation time with the optional --pg-num-min <num> argument to the ceph osd pool create command.

## A preselection of pg_num¶

When creating a new pool with:

ceph osd pool create {pool-name} [pg_num]

it is optional to choose the value of pg_num. If you do not specify pg_num, the cluster can (by default) automatically tune it for you based on how much data is stored in the pool (see above, Autoscaling placement groups).

Alternatively, pg_num can be explicitly provided. However, whether you specify a pg_num value or not does not affect whether the value is automatically tuned by the cluster after the fact. To enable or disable auto-tuning,:

ceph osd pool set {pool-name} pg_autoscale_mode (on|off|warn)

The “rule of thumb” for PGs per OSD has traditionally be 100. With the additional of the balancer (which is also enabled by default), a value of more like 50 PGs per OSD is probably reasonable. The challenge (which the autoscaler normally does for you), is to:

• have the PGs per pool proportional to the data in the pool, and

• end up with 50-100 PGs per OSDs, after the replication or erasuring-coding fan-out of each PG across OSDs is taken into consideration

## How are Placement Groups used ?¶

A placement group (PG) aggregates objects within a pool because tracking object placement and object metadata on a per-object basis is computationally expensive–i.e., a system with millions of objects cannot realistically track placement on a per-object basis.

The Ceph client will calculate which placement group an object should be in. It does this by hashing the object ID and applying an operation based on the number of PGs in the defined pool and the ID of the pool. See Mapping PGs to OSDs for details.

The object’s contents within a placement group are stored in a set of OSDs. For instance, in a replicated pool of size two, each placement group will store objects on two OSDs, as shown below.

Should OSD #2 fail, another will be assigned to Placement Group #1 and will be filled with copies of all objects in OSD #1. If the pool size is changed from two to three, an additional OSD will be assigned to the placement group and will receive copies of all objects in the placement group.

Placement groups do not own the OSD; they share it with other placement groups from the same pool or even other pools. If OSD #2 fails, the Placement Group #2 will also have to restore copies of objects, using OSD #3.

When the number of placement groups increases, the new placement groups will be assigned OSDs. The result of the CRUSH function will also change and some objects from the former placement groups will be copied over to the new Placement Groups and removed from the old ones.

Data durability and even distribution among all OSDs call for more placement groups but their number should be reduced to the minimum to save CPU and memory.

### Data durability¶

After an OSD fails, the risk of data loss increases until the data it contained is fully recovered. Let’s imagine a scenario that causes permanent data loss in a single placement group:

• The OSD fails and all copies of the object it contains are lost. For all objects within the placement group the number of replica suddenly drops from three to two.

• Ceph starts recovery for this placement group by choosing a new OSD to re-create the third copy of all objects.

• Another OSD, within the same placement group, fails before the new OSD is fully populated with the third copy. Some objects will then only have one surviving copies.

• Ceph picks yet another OSD and keeps copying objects to restore the desired number of copies.

• A third OSD, within the same placement group, fails before recovery is complete. If this OSD contained the only remaining copy of an object, it is permanently lost.

In a cluster containing 10 OSDs with 512 placement groups in a three replica pool, CRUSH will give each placement groups three OSDs. In the end, each OSDs will end up hosting (512 * 3) / 10 = ~150 Placement Groups. When the first OSD fails, the above scenario will therefore start recovery for all 150 placement groups at the same time.

The 150 placement groups being recovered are likely to be homogeneously spread over the 9 remaining OSDs. Each remaining OSD is therefore likely to send copies of objects to all others and also receive some new objects to be stored because they became part of a new placement group.

The amount of time it takes for this recovery to complete entirely depends on the architecture of the Ceph cluster. Let say each OSD is hosted by a 1TB SSD on a single machine and all of them are connected to a 10Gb/s switch and the recovery for a single OSD completes within M minutes. If there are two OSDs per machine using spinners with no SSD journal and a 1Gb/s switch, it will at least be an order of magnitude slower.

In a cluster of this size, the number of placement groups has almost no influence on data durability. It could be 128 or 8192 and the recovery would not be slower or faster.

However, growing the same Ceph cluster to 20 OSDs instead of 10 OSDs is likely to speed up recovery and therefore improve data durability significantly. Each OSD now participates in only ~75 placement groups instead of ~150 when there were only 10 OSDs and it will still require all 19 remaining OSDs to perform the same amount of object copies in order to recover. But where 10 OSDs had to copy approximately 100GB each, they now have to copy 50GB each instead. If the network was the bottleneck, recovery will happen twice as fast. In other words, recovery goes faster when the number of OSDs increases.

If this cluster grows to 40 OSDs, each of them will only host ~35 placement groups. If an OSD dies, recovery will keep going faster unless it is blocked by another bottleneck. However, if this cluster grows to 200 OSDs, each of them will only host ~7 placement groups. If an OSD dies, recovery will happen between at most of ~21 (7 * 3) OSDs in these placement groups: recovery will take longer than when there were 40 OSDs, meaning the number of placement groups should be increased.

No matter how short the recovery time is, there is a chance for a second OSD to fail while it is in progress. In the 10 OSDs cluster described above, if any of them fail, then ~17 placement groups (i.e. ~150 / 9 placement groups being recovered) will only have one surviving copy. And if any of the 8 remaining OSD fail, the last objects of two placement groups are likely to be lost (i.e. ~17 / 8 placement groups with only one remaining copy being recovered).

When the size of the cluster grows to 20 OSDs, the number of Placement Groups damaged by the loss of three OSDs drops. The second OSD lost will degrade ~4 (i.e. ~75 / 19 placement groups being recovered) instead of ~17 and the third OSD lost will only lose data if it is one of the four OSDs containing the surviving copy. In other words, if the probability of losing one OSD is 0.0001% during the recovery time frame, it goes from 17 * 10 * 0.0001% in the cluster with 10 OSDs to 4 * 20 * 0.0001% in the cluster with 20 OSDs.

In a nutshell, more OSDs mean faster recovery and a lower risk of cascading failures leading to the permanent loss of a Placement Group. Having 512 or 4096 Placement Groups is roughly equivalent in a cluster with less than 50 OSDs as far as data durability is concerned.

Note: It may take a long time for a new OSD added to the cluster to be populated with placement groups that were assigned to it. However there is no degradation of any object and it has no impact on the durability of the data contained in the Cluster.

### Object distribution within a pool¶

Ideally objects are evenly distributed in each placement group. Since CRUSH computes the placement group for each object, but does not actually know how much data is stored in each OSD within this placement group, the ratio between the number of placement groups and the number of OSDs may influence the distribution of the data significantly.

For instance, if there was a single placement group for ten OSDs in a three replica pool, only three OSD would be used because CRUSH would have no other choice. When more placement groups are available, objects are more likely to be evenly spread among them. CRUSH also makes every effort to evenly spread OSDs among all existing Placement Groups.

As long as there are one or two orders of magnitude more Placement Groups than OSDs, the distribution should be even. For instance, 256 placement groups for 3 OSDs, 512 or 1024 placement groups for 10 OSDs etc.

Uneven data distribution can be caused by factors other than the ratio between OSDs and placement groups. Since CRUSH does not take into account the size of the objects, a few very large objects may create an imbalance. Let say one million 4K objects totaling 4GB are evenly spread among 1024 placement groups on 10 OSDs. They will use 4GB / 10 = 400MB on each OSD. If one 400MB object is added to the pool, the three OSDs supporting the placement group in which the object has been placed will be filled with 400MB + 400MB = 800MB while the seven others will remain occupied with only 400MB.

### Memory, CPU and network usage¶

For each placement group, OSDs and MONs need memory, network and CPU at all times and even more during recovery. Sharing this overhead by clustering objects within a placement group is one of the main reasons they exist.

Minimizing the number of placement groups saves significant amounts of resources.

## Choosing the number of Placement Groups¶

If you have more than 50 OSDs, we recommend approximately 50-100 placement groups per OSD to balance out resource usage, data durability and distribution. If you have less than 50 OSDs, choosing among the preselection above is best. For a single pool of objects, you can use the following formula to get a baseline

Total PGs = $$\frac{OSDs \times 100}{pool \: size}$$

Where pool size is either the number of replicas for replicated pools or the K+M sum for erasure coded pools (as returned by ceph osd erasure-code-profile get).

You should then check if the result makes sense with the way you designed your Ceph cluster to maximize data durability, object distribution and minimize resource usage.

The result should always be rounded up to the nearest power of two.

Only a power of two will evenly balance the number of objects among placement groups. Other values will result in an uneven distribution of data across your OSDs. Their use should be limited to incrementally stepping from one power of two to another.

As an example, for a cluster with 200 OSDs and a pool size of 3 replicas, you would estimate your number of PGs as follows

$$\frac{200 \times 100}{3} = 6667$$. Nearest power of 2: 8192

When using multiple data pools for storing objects, you need to ensure that you balance the number of placement groups per pool with the number of placement groups per OSD so that you arrive at a reasonable total number of placement groups that provides reasonably low variance per OSD without taxing system resources or making the peering process too slow.

For instance a cluster of 10 pools each with 512 placement groups on ten OSDs is a total of 5,120 placement groups spread over ten OSDs, that is 512 placement groups per OSD. That does not use too many resources. However, if 1,000 pools were created with 512 placement groups each, the OSDs will handle ~50,000 placement groups each and it would require significantly more resources and time for peering.

You may find the PGCalc tool helpful.

## Set the Number of Placement Groups¶

To set the number of placement groups in a pool, you must specify the number of placement groups at the time you create the pool. See Create a Pool for details. Even after a pool is created you can also change the number of placement groups with:

ceph osd pool set {pool-name} pg_num {pg_num}

After you increase the number of placement groups, you must also increase the number of placement groups for placement (pgp_num) before your cluster will rebalance. The pgp_num will be the number of placement groups that will be considered for placement by the CRUSH algorithm. Increasing pg_num splits the placement groups but data will not be migrated to the newer placement groups until placement groups for placement, ie. pgp_num is increased. The pgp_num should be equal to the pg_num. To increase the number of placement groups for placement, execute the following:

ceph osd pool set {pool-name} pgp_num {pgp_num}

When decreasing the number of PGs, pgp_num is adjusted automatically for you.

## Get the Number of Placement Groups¶

To get the number of placement groups in a pool, execute the following:

ceph osd pool get {pool-name} pg_num

## Get a Cluster’s PG Statistics¶

To get the statistics for the placement groups in your cluster, execute the following:

ceph pg dump [--format {format}]

Valid formats are plain (default) and json.

## Get Statistics for Stuck PGs¶

To get the statistics for all placement groups stuck in a specified state, execute the following:

ceph pg dump_stuck inactive|unclean|stale|undersized|degraded [--format <format>] [-t|--threshold <seconds>]

Inactive Placement groups cannot process reads or writes because they are waiting for an OSD with the most up-to-date data to come up and in.

Unclean Placement groups contain objects that are not replicated the desired number of times. They should be recovering.

Stale Placement groups are in an unknown state - the OSDs that host them have not reported to the monitor cluster in a while (configured by mon_osd_report_timeout).

Valid formats are plain (default) and json. The threshold defines the minimum number of seconds the placement group is stuck before including it in the returned statistics (default 300 seconds).

## Get a PG Map¶

To get the placement group map for a particular placement group, execute the following:

ceph pg map {pg-id}

For example:

ceph pg map 1.6c

Ceph will return the placement group map, the placement group, and the OSD status:

osdmap e13 pg 1.6c (1.6c) -> up [1,0] acting [1,0]

## Get a PGs Statistics¶

To retrieve statistics for a particular placement group, execute the following:

ceph pg {pg-id} query

## Scrub a Placement Group¶

To scrub a placement group, execute the following:

ceph pg scrub {pg-id}

Ceph checks the primary and any replica nodes, generates a catalog of all objects in the placement group and compares them to ensure that no objects are missing or mismatched, and their contents are consistent. Assuming the replicas all match, a final semantic sweep ensures that all of the snapshot-related object metadata is consistent. Errors are reported via logs.

To scrub all placement groups from a specific pool, execute the following:

ceph osd pool scrub {pool-name}

## Prioritize backfill/recovery of a Placement Group(s)¶

You may run into a situation where a bunch of placement groups will require recovery and/or backfill, and some particular groups hold data more important than others (for example, those PGs may hold data for images used by running machines and other PGs may be used by inactive machines/less relevant data). In that case, you may want to prioritize recovery of those groups so performance and/or availability of data stored on those groups is restored earlier. To do this (mark particular placement group(s) as prioritized during backfill or recovery), execute the following:

ceph pg force-recovery {pg-id} [{pg-id #2}] [{pg-id #3} ...]
ceph pg force-backfill {pg-id} [{pg-id #2}] [{pg-id #3} ...]

This will cause Ceph to perform recovery or backfill on specified placement groups first, before other placement groups. This does not interrupt currently ongoing backfills or recovery, but causes specified PGs to be processed as soon as possible. If you change your mind or prioritize wrong groups, use:

ceph pg cancel-force-recovery {pg-id} [{pg-id #2}] [{pg-id #3} ...]
ceph pg cancel-force-backfill {pg-id} [{pg-id #2}] [{pg-id #3} ...]

This will remove “force” flag from those PGs and they will be processed in default order. Again, this doesn’t affect currently processed placement group, only those that are still queued.

The “force” flag is cleared automatically after recovery or backfill of group is done.

Similarly, you may use the following commands to force Ceph to perform recovery or backfill on all placement groups from a specified pool first:

ceph osd pool force-recovery {pool-name}
ceph osd pool force-backfill {pool-name}

or:

ceph osd pool cancel-force-recovery {pool-name}
ceph osd pool cancel-force-backfill {pool-name}

to restore to the default recovery or backfill priority if you change your mind.

Note that these commands could possibly break the ordering of Ceph’s internal priority computations, so use them with caution! Especially, if you have multiple pools that are currently sharing the same underlying OSDs, and some particular pools hold data more important than others, we recommend you use the following command to re-arrange all pools’s recovery/backfill priority in a better order:

ceph osd pool set {pool-name} recovery_priority {value}

For example, if you have 10 pools you could make the most important one priority 10, next 9, etc. Or you could leave most pools alone and have say 3 important pools all priority 1 or priorities 3, 2, 1 respectively.

## Revert Lost¶

If the cluster has lost one or more objects, and you have decided to abandon the search for the lost data, you must mark the unfound objects as lost.

If all possible locations have been queried and objects are still lost, you may have to give up on the lost objects. This is possible given unusual combinations of failures that allow the cluster to learn about writes that were performed before the writes themselves are recovered.

Currently the only supported option is “revert”, which will either roll back to a previous version of the object or (if it was a new object) forget about it entirely. To mark the “unfound” objects as “lost”, execute the following:

ceph pg {pg-id} mark_unfound_lost revert|delete

Important

Use this feature with caution, because it may confuse applications that expect the object(s) to exist.


text:
# Does $\varphi(1)=1$ if $\varphi$ is a field homomorphism?

Is it by definition that $\varphi(1)=1$ if $\varphi$ is a field homomorphism ?

My field theory lecture said that yes, but now $\varphi\equiv0$ is not a field homomorphism...

What is the 'standard' in mathematics ? (i.e. if someone says that $\varphi$ is a field homomorphism does it imply $\varphi(1)=1$ ?)

-
It is standard to assume $\varphi(1) = 1$. It isn't hard to show that if $\varphi(1)\neq 1$, then $\varphi\equiv 0$. Thus assuming $\varphi(1) = 1$ is just to rule out this case. –  froggie May 6 '12 at 14:25
Why would you want $0$ to be a homomorphism? It's not like you can add field (or ring) homomorphisms. –  Zhen Lin May 6 '12 at 14:39
Hi, it seems that my answer is somewhat misleading and possibly even wrong. Please unaccept it so I can delete the answer. Pete Clark has agreed to write an answer of his own, which I am sure will be much better than mine. –  Asaf Karagila May 6 '12 at 17:40
@AsafKaragila - done. –  Belgi May 6 '12 at 18:17

Upon request, I am leaving an answer.

First, let's acknowledge that this is a question about conventions first and only secondarily about mathematics. Your lecturer's definition of a field homomorphism is whatever she says it is: that's what a definition means. ("When I use a word, it means just what I choose it to mean -- neither more nor less." -- Humpty Dumpty) On the other hand, definitions, while in some formal sense arbitrary, can certainly be good or bad, for both mathematical and sociological reasons.

Your lecturer's definition is a good one both because of its mathematical consequences and because, as she claimed, this is very much the "standard" definition, i.e., the one you will find in the vast majority of contemporary texts and courses, the one which is being used by practitioners both in field theory itself and in areas of mathematics where field theory is applied, and so forth.

The notion of "homomorphism" is so important in mathematics that there has been a lot of effort to make it as systematic and "un-(ad hoc)" as possible. Two very general frameworks for discussing homomorphisms are universal algebra and category theory. The basic objects of study in universal algebra are relational structures, namely sets equipped with various relations (and, what is a special case of that, functions), of various "arities".

From this perspective, the relational structure of a ring is a set $R$, two binary operations called $+$ and $\cdot$ and two "nullary functions" -- i.e., constants $0$ and $1$. There is more to the definition of a ring, namely the axioms that these relations must satisfy. In this sense, model theory is being overlayed on top of universal algebra. However, the definition of a homomorphism of relational structures doesn't depend on the axioms: a homomorphism of relational structures is just a map of the underlying sets which preserves, in a rather straightforward sense which I won't completely write out here (one can easily look it up online) all the relations. In the case of rings, this means that a homomorphism $f: R \rightarrow S$ is a map of the underlying sets such that

$\bullet$ For all $x,y \in R$, $f(x+y) = f(x) + f(y)$,
$\bullet$ For all $x,y \in R$, $f(x \cdot y) = f(x) \cdot f(y)$,
$\bullet$ $f(0) =0$, and
$\bullet$ $f(1) = 1$.

Again, I stress that this does not depend on the axioms (or, in more model-theoretic terminology, the theory, of the structure): a homomorphism of non-associative rings (with distinguished elements $0$ and $1$) is the same definition as a homomorphism of not necessarily commutative rings, which is the same definition as a homomorphism of fields. This uniformity is useful and powerful.

Now let $f: R \rightarrow S$ be a homomorphism of rings. An element $x \in R$ is a unit if there exists $y \in R$ such that $xy = yx = 1$. Two easy facts:

(i) For all $x \in R$, there is at most one $y \in R$ such that $xy = yx = 1$.
(Proof: If also $xz = zx = 1$, then $y = y \cdot 1 = y(xz) = (yx)z = 1 \cdot z = z$.)

Thus if $x$ is a unit, it has a well-defined inverse which we may denote $x^{-1}$. However, $x \mapsto x^{-1}$ is not a completely kosher function from the perspective of universal algebra, since it is not a function on $R$ but only on $R^{\times}$, the set of units of $R$. There are ways to get around this (a keyword is sorts) but the easiest solution is simply not to regard $x \mapsto x^{-1}$ is being part of the relational structure defining a commutative ring.

(ii) If $f: R \rightarrow S$ is a homomorphism of rings and $x \in R^{\times}$, then $f(x) \in S^{\times}$ and $f(x^{-1}) = f(x)^{-1}$.
(Proof: $f(x^{-1}) f(x) = f(x^{-1} x) = f(1) = 1 = f(1) = f(x x^{-1}) = f(x) f(x^{-1})$.)

Thus the preservation of inverses comes for free from this definition of ring homomorphisms.

There is also the categorical perspective, which is more general and thus more permissive. It has the bright idea that in the same breath as we define a mathematical object of a certain kind ("category"!), we should define the notion of homomorphism between objects of that category. In order to be a homomorphism, certain very mild axioms of composition and identities must be satisfied. So in particular, there is a category $\operatorname{Ring}$ in which the objects are rings and the morphisms are defined exactly as above. But there is also a category $\operatorname{Rng}$ in which the objects are "rngs", i.e., what you get by taking the constant $1$ out of the relational structure and taking out all the parts of the axioms for rings which refer to it. And there is even the category -- call it $\operatorname{Ring}'$ -- in which the objects are rings -- i.e., have $1$ -- but in which homomorphisms are not required to carry $1$ to $1$. In particular, for any rings $R$ and $S$, the identically zero map from $R$ to $S$ is a homomorphism in $\operatorname{Ring}'$ but not in $\operatorname{Ring}$ (except in the trivial case where $0 = 1$ in $S$).

It is worth spending a little time getting experience with the category $\operatorname{Ring}'$, both because (i) it is not simply a pathology: these sorts of maps between rings do come up sometimes and (ii) it gives you insight about the much more standard category $\operatorname{Ring}$. In particular, for a homomorphism $f: R \rightarrow S$ in $\operatorname{Ring}'$ $f(1)$ cannot be just any old element of $S$ but must be an idempotent element:

$f(1) = f(1 \cdot 1) = f(1) \cdot f(1)$.

Many rings have only $0$ and $1$ as idempotents -- in particular, this holds for fields -- so either $f(1) = 1$, in which case we're back to the standard case, or $f(1) = 0$, and in this case for all $x \in R$, $f(x) = f(x \cdot 1) = f(x) \cdot f(1) = f(x) \cdot 0 = 0$, so $f$ is identically zero.

So now we know exactly what we're excluding by defining a homomorphism of fields to satisfy $f(1) = 1$: we're excluding the identically zero map between fields. So we can be rather confident that we're not excluding anything important: certainly the zero map is not interesting in its own right, just as the identity element of a group or zero element of a ring is not really interesting in its own right. However, the identity element of a group and zero element of a ring are there for another very important reason: they enable the appropriate algebraic structure of group or ring to exist!

In contrast, if $R$ and $S$ are rings, then I see no intrinsic algebraic structure on the set of homomorphisms from $R$ to $S$: we cannot add them, multiply them (so as to get another homomorphism from $R$ to $S$) and so forth. So adding the zero element is not helping us in any evident way. In fact, if we don't believe this at first, no matter -- keep it in and see what happens. We'll find that in our further study of field theory, we'll keep having to say "except for the zero homomorphism" in results and arguments. For instance, most of field theory is based upon the fact that absolutely every field homomorphism $\iota: E \rightarrow F$ is injective and makes $F$ into an $E$-vector space...except for the zero homomorphism.

-


text:
💬 👋 We’re always here. Join our Discord to connect with other students 24/7, any time, night or day.Join Here!

JH

# In the figure at the right there are infinitely many circles approaching the vertices of an equilateral triangle, each circle touching other circles and sides of the triangle. If the triangle has sides of length 1, find the total area occupied by the circles.

## $\frac{11 \pi}{96}$

Sequences

Series

### Discussion

You must be signed in to discuss.

Lectures

Join Bootcamp

JH

Sequences

Series

Lectures

Join Bootcamp


text:
Configuring QNAP

Friday, May 7, 2021

Notes on how to configure QNAP. The system is not intuitive at all.

Top


text:
# Using ‘kraken’ Computational Cluster¶

## Introduction¶

One of the main purposes of the kraken cluster is to accommodate especially long-running programs. Users who run long jobs (which take hours or days to run) will need to run these jobs through the Torque Scheduler. Torque provides a method for handling these jobs on a first-come first-served basis with additional fairshare policy so all users can have their jobs started in some reasonable time. In this manner, all jobs will run more efficiently and finish quicker since each is allowed to have all system resources for the duration of its run. All Torque jobs must be launched from the kraken server.

## The Most Common Commands¶

The basic commands provided by Torque for starting and stopping jobs and for manipulating jobs in queues are shown below. For complete manual of Torque command, type “man <cmd>” (e.g. “man qsub”). These command are:

• qsub — the basic command for running jobs,
• qstat — show currently running jobs/queued jobs,
• qnodes — gives the current status of all nodes,
• qpeek — allows to see the current output of the job in progress,
• qhold and qrls — allow to hold and release the running job.

## How to Run a Batch Job¶

The Torque Scheduler will not accept any program directly. It is designed instead to accept a shell script — a .sh file — which itself runs the commands necessary to launch your program. Once your script is ready, you can submit it to Torque with the qsub command:

$qsub your_script.sh  Mind that you do not enter$ symbol as it is a part of the prompt. When this command is issued, you will be given a job number, we will call it XX in this example, which is used for tracking and manipulating your job. Standard out and standard error from the job will be copied to files in your current directory named your_script.sh.oXX and your_script.sh.eXX for your reference.

You can specify the queue to which your job is assigned by giving it after parameter -q. The available queues are specified in the table below. They differ by the default number of processors and memory assigned to your job. If you want different number of resources than queue default, you can specify them using parameter -l. Note, however, that you cannot increase the maximum constrains of the chosen queue, although you are welcome to decrease the required resources. In the following example, the test1.sh script requires 4 nodes in order to run and the calculations are supposed to take more time than 2.5h, so it is assigned to queue longer4. However, the required memory is only 4GB (instead of the default 12GB). Hence, such a job can be submitted with the command:

$qsub -q longer4 -l mem=4GB test1.sh  Once this command is issued, the system will verify that there is a machine with 4 processor and 4GB of memory ready for use. If there is, it will allocate 4 processors for this job and the job will run. If 4 processors or 4GB of free memory are not yet available, the job will be put in the queue. The most popular resources that can be requested are specified in the table at the end of this page. More details of the qsub command are specified in the appendix. ## Monitoring Jobs¶ A user can issue the qstat command to track the status of the job. In the example below, the status of this job is shown as “R” (Running). A job can also show a status of “Q” (Queued), “H” (Hold), or “C” (Completed). The sample output of the qstat command looks as follows: maciek@kraken:$ qstat

Job id                    Name             User            Time Use S Queue
------------------------- ---------------- --------------- -------- - -----
3177.kraken               test1.sh         maciek          00:01:28 R quick4

## Job Arrays¶

To submit a large number of similar cluster jobs, there are two basic approaches. A shell script can be used to repeatedly call qsub passing in a customized PBS script (either by creating a temporary PBS script file or by piping the PBS commands into qsub).

The preferred approach–that is simpler and potentially more powerfull–would be to submit a job array using one PBS script and a single call to qsub. Job arrays hand-off the management of large numbers of similar jobs to the Resource Manager and Scheduler and provide a mechanism that allows cluster users to reference an entire set of jobs as though it were a single cluster job.

### Submitting Job Arrays¶

Job arrays are submitted by including the -t option in a call to qsub, or by including the #PBS -t command in your PBS script. The -t option takes a comma-delimited list of job ID numbers or of one or more pairs of job ID numbers separated by a dash.

Each job in the job array will be launched with the same PBS script and in an identical environment–except for the value of its array ID. The value of the Array ID for each job in a Job Array is stored in the PBS_ARRAYID environment variable.

For example, if a job array is submitted with 10 elements, numbered from 1 to 10, the submission command would be the following:

$qsub -t 1-10 array_script.sh  An optional parameter, the slot limit, can be added to the end of the -t option to specify the maximum number of job array elements that can run at one time. The slot limit is specified by appending a “%” to the -t option followed by the slot limit value. A twelve element job array with non-sequential array IDs and a slot limit of 3 could be specified as follows: $ qsub -t 1-3,5-7,9-11,13-15%3 array_script.sh

Each job included in the job array has its own unique array element value stored in the PBS_ARRAYID environment variable. The value of each job array element’s array ID can be accessed by the job script just like any other shell environment variable. If the job ran a bash shell script, the job’s array ID information could printed to STDOUT using the following command:

echo "Current job array element's Array ID: ${PBS_ARRAYID}"  ### Customizing Data for Job Array Elements¶ A more useful task for the array ID–and the real power of job arrays–would be to use the job’s Array ID as a direct or indirect index into the data being processed by the job array. One approach to accomplish this would be to use the PBS_ARRAYID value to provide a custom set of input parameters for job in the job array. To do this, a text file would be created containing multiple lines each of which would consist of a series of space delimited values. In this approach, each line in the data file would contain the input parameters needed by one element of the job array. The PBS script would then be modifed to include a command that would read in the correct line of the data file–based on the PBS_ARRAYID value of that particular job. While there are many ways to read the appropriate line from the data file, the following serves as a sample implementation assuming that the data file was called data.dat and was located in the same directory as the script that was run for each element of the job array: PARAMETERS=$(sed "${PBS_ARRAYID}q;d" data.dat)  Assuming that the excecutable program/script for the jobs in this array was called command.sh, the PBS script would launch the program with a line like the following: command.sh${PARAMETERS}

An alternate approach is possible if the unique input parameters needed by each job in the array can be calculated arithmetically. For example, if each instance of the command.sh script needed to loop over a range of values, the PBS script could calcuate the max and min values needed for each job directly–based on the value in the PBS_ARRAYID environment variable. If each job’s range needed to include 1000 values, this could be done by including commands like the following in the PBS script:

MAX=$(echo "${PBS_ARRAYID}*1000" | bc)
MIN=$(echo "(${PBS_ARRAYID}-1)*1000" | bc)

The data file referred to above (data.dat) would not be needed in this approach, and the PBS script call to command.sh would be something like the following:

command.sh ${MIN}${MAX}

# Appendix — Details on Basic Commands¶

## qsub¶

The qsub command submits a sequence of commands to the batch server along with the parameters specifying job resource requirements. The parameters may be provided on the command line, from within the job script, or a combination of both. To facilitate optimal scheduling, you should specify as many resources as possible.

The syntax for the qsub command is:

qsub [ option(s) ] [ script-file ]

The typical options are:

-q queue

The queue to which the job is sent. Different queues allow different default and maximum resources that can be allocated to the job and have different priorities. The list of all the queues in kraken are shown in the table below.

Note

If this parameter is missing, the job will be submitted to the default queue quick1.

-N name

The name of the job. If this option is not specified, the job is named after your script-file.

-l resources_list

Comma-separated list of requested resources. The list of the most popular resources are shown in the table.

-o stdout_file_name

File name of the standard output (STDOUT) of your job. The file specified in this option will be used instead of the default one.

-e stderr_file_name

File name of the standard error and log messages (STDERR) of your job. The file specified in this option will be used instead of the default one.

-t array_specification

The specification of the array i.e. a bunch of similar jobs run with the same script. See qsub manual for details.

Specfies the arguments that will be passed to the job script when the script is launched. The accepted syntax is:

qsub -F "myarg1 myarg2 myarg3=myarg3value" myscript2.sh

Warning

Quotation marks are required. qsub will fail with an error message if the argument following -F is not a quoted value. The server will pass the quoted value as arguments to the job script when it launches the script.

Mail notification options. The behavior of email notifications is set by combinations of the letters “a”, “b”, “e”, and “n” provided to the -m qsub flag. The options for email notifications are:

 “a” (abort) email is sent when job errors are encountered, “b” (begin) email is sent when jobs begin, “e” (end) email is sent when jobs end, “n” (never) no email is sent.

For large numbers of jobs, the recommended setting is -m a which will provide notification only if there is an error.

The qsub options can be also specified in the beginning of your script, by putting them in the comment lines starting with #PBS (see the sample script below).

Note

Define requested resources carefully, by assigning your jobs to the proper queue and using -l switch to reduce required resources (on Kraken you are not allowed to increase the default queue resources). Mind that, on the one hand, your job will be killed if it does ot fit within specified constraints, however, on the other hand, smaller jobs will have higher priority and will start execution sooner.

### Examples of qsub Invocation¶

qsub -q longer4 your_script.sh
(sent your script to longer4 queue),
qsub -N my_job your_script.sh
(sent your script to the default queue and name it my_job),
qsub -l nodes=4:mem=2gb,walltime=1:00:00 your_script.sh
(requests four nodes, 2gb required per node, and a maximum runtime of 1 hour),
qsub -l nodes=node1+node2 your_script.sh
(requests 2 specific nodes),
qsub -l nodes=node0+2 your_script.sh
(requests node0 and any other 2 nodes),
qsub -l nodes=1:ppn=3 -N my_job your_script.sh
(requests 3 processors on one node and name the job my_job),
qsub -l nodes=node1:ppn=4 your_script.sh
(requests 4 processors on the specific node).
qsub -l other=bigdisk your_script.sh
(requests large temporary disk (1.7 TB) on the computing node).

### Sample Submission Script¶

#!/bin/bash
#PBS -N my\_job\_name
#PBS -q longer4
#PBS -l other=bigdisk
#PBS -t 1-10
#PBS -m e
#PBS -M kraken.user@p.lodz.pl
plask input.xpl ${PBS_ARRAYID}  ## qstat¶ The qstat command monitors the status of all jobs currently submitted to Torque on the kraken cluster. ### Examples:¶ qstat (show all jobs), qstat -a (show all jobs, alternate format), qstat -n1 (show all jobs, alternate format with specification of the nodes where the job runs), qstat -t (show all jobs without grouping arrays), qstat -f 1234 (show detailed information about job 1234). qstat -f 1234[3] (show detailed information about job number 3 of the array with ID 1234). ## qdel¶ A queued job may be removed from a queue or a running job may be killed using the qdel command. ### Example¶ qdel 1234 (delete job with ID 1234; the job ID can be obtained with the qstat command). qdel 1234[] (delete all jobs from the array with ID 1234). qdel 1234[3] (delete job number 3 from the array with ID 1234). ## qpeek¶ You can see the current output of a running job by running command qpeek. ### Examples¶ qpeek 1234 (show the standard output and standard error of job 1234), qpeek -o 1234.kraken (show only the standard output of job 1234), qpeek -e 1234 (show only standard error of job 1234), qpeek -N myjob (show the standard output and standard error of job named myjob). ## qhold and qrls¶ Kraken cluster supports job checkpointing i.e. saving the state of the job to disk. This allows the job to be suspended (hold) on a user request and resumed (released) later. This feature can be useful in case you have a big long-running job and want to suspend it in order to make space for more urgent smaller jobs. Jobs can be hold using command qhols and released with qrls. ### Examples¶ qhold 1234 (hold job 1234), qrls 1234 (release job 1234). # Tables¶ Queues defined on Kraken cluster The following table contains a list of the queues available at Kraken cluster. Use the one that suits your needs best. Queues multi16 and multi32 are reserved for MPI jobs. Queue name nodes/ppn walltime mem tiny1 1 / 1 2.5 h 1 GB tiny4 1 / 4 2.5 h 4 GB quick1 1 / 1 2.5 h 3 GB quick4 1 / 4 2.5 h 12 GB quick8 1 / 8 2.5 h 24 GB longer1 1 / 1 13 h 3 GB longer4 1 / 4 13 h 12 GB longer8 1 / 8 13 h 24 GB thelongest1 1 / 1 7 days 3 GB thelongest4 1 / 4 7 days 12 GB thelongest8 1 / 8 7 days 24 GB multi16 16 / 1 7 days 16 × 3 GB multi32 32 / 1 7 days 32 × 3 GB nodes: number of used nodes, ppn: number of processor per nodes, walltime: total execution time, mem: total allowed memory usage The most common resources that can be specified with -l switch -l option Action walltime=hh:mm:ss The length of time your job will need to run. Your job will end after the allocated walltime has expired whether it is finished or not, so choose this value carefully. Appropriate walltime should be chosen in order to prevent programs hat either run out of control, or who never exit, from consuming all system resources. mem=N[measure] The maximum amount of memory the job is expected to use. The measure may be in GB, MB, KB, B. nodes=n Specifies the number of nodes or the specific node required. nodes=n:ppn=x Specifies the number of nodes or the specific node required and allocate x processors per node (ppn). other=bigdisk Special property of the computing node. bigdisk means that your job will be run on a server with 1.7 TB of temporary space (mounted in /tmp). Environment variables available to execution scipts Variable name Description PBS_O_HOST The name of the host upon which the qsub command is running. PBS_SERVER The hostname of the pbs_server which qsub submits the job to. PBS_O_QUEUE The name of the original queue to which the job was submitted. PBS_O_WORKDIR The absolute path of the current working directory of the qsub command. PBS_ARRAYID Each member of a job array is assigned a unique identifier (see -t option). PBS_JOBID The job identifier assigned to the job by the batch system. It can be used in the stdout and stderr paths. The batch system replaces$PBS_JOBID with the job’s jobid (for example, #PBS -o /tmp/\$PBS_JOBID.output).
PBS_JOBNAME The job name supplied by the user.
PBS_QUEUE The name of the queue from which the job is executed.


text:
# Magnetic Field due to a current loop

1. Mar 3, 2008

### snoweangel27

[SOLVED] Magnetic Field due to a current loop

1. The problem statement, all variables and given/known data

A single loop of wire of radius 3 cm carries a current of 2.6 A. What is the magnitude of B on the axis of the loop at 2 cm?

2. Relevant equations

B=$$\mu$$/(4$$\pi$$) * 2$$\pi$$(R^2)*I/(z^2+R^2)^(3/2)

3. The attempt at a solution
I = 2.6 A
R = .03 m
z = .02m

I calculate .000031 T
It should just be a simple matter of plugging in numbers, but every time I use this equation it ends up being wrong. If anyone could tell me what I might be doing wrong it would be greatly appreciated.

2. Mar 3, 2008

### Staff: Mentor

Looks OK to me. Why do you think it's wrong?

3. Mar 3, 2008

### snoweangel27

It is computerized homework, so when I put in the answer that I calculated it keeps telling me that it is wrong. I have done the same thing with multiple different distances, and they all come up wrong, so I believe that it is something that I am doing, I am just not sure what

4. Mar 3, 2008

### Staff: Mentor

Those online systems can be flaky. I don't think you're doing anything wrong. Your equation is correct and your answer is correct.

Things to check: Are you sure they want the answer in Teslas? How many sig figs does the system like?

5. Mar 3, 2008

### snoweangel27

I finally figured it out. It turns out that the system decided it wanted it in scientific notation. Thanks for your help!


text:
# zbMATH — the first resource for mathematics

Local tube realizations of CR-manifolds and maximal abelian subalgebras. (English) Zbl 1229.32020
A tube CR-submanifold in $$\mathbb C^r$$ is a smooth submanifold of the form $$T_F:=\mathbb R^r+iF$$, where $$F\subset\mathbb R^r$$ is a real submanifold called the base of $$T_f$$. These submanifolds serve as test cases in several questions of CR geometry. The main aim of this article is to give necessary and sufficient conditions for a general submanifold $$M$$ to be, locally around a point $$a\in M$$, isomorphic to some tube CR-submanifold, and to study the question of uniqueness of such a realization. This is done in the analytic category.
The key ingredient in the study of these problems is that the translations in real directions evidently give rise to an $$r$$-dimensional commutative subalgebra in the Lie algebra of infinitesimal CR-automorphisms. The authors first characterize when such a subalgebra comes from a tube realization. In the uniqueness question, it turns out that there are two interesting notions of (local) equivalence for local tube realizations. It is shown that they correspond to conjugacy of the abelian subalgebras under two different groups. Several examples are studied in detail.
Reviewer: Andreas Cap (Wien)

##### MSC:
 32V05 CR structures, CR operators, and generalizations 32V40 Real submanifolds in complex manifolds 32M25 Complex vector fields, holomorphic foliations, $$\mathbb{C}$$-actions
Full Text:


text:
# Illustration Wave function in the classically forbidden / allowed region

Get illustration

Share — copy and redistribute the material in any medium or format

Adapt — remix, transform, and build upon the material for any purpose, even commercially.

Sharing and adapting of the illustration is allowed with indication of the link to the illustration.

Example of a wave function that penetrates into a classically forbidden region (red). The wave function oscillates in the classically allowed region (blue) between $$x_1$$ and $$x_2$$. In classically forbidden region the wave function runs towards positive or negative infinity. For certain total energies $$W$$ of the particle, the wave function decreases exponentially. This property of the wave function enables the quantum tunneling.

In the classically allowed region between $$x_1$$ and $$x_2$$, the signs of the wave function $$\mathit{\Psi}(x)$$ and the curvature $$\frac{\partial^2 \mathit{\Psi}(x) }{\partial x^2}$$ (second spatial derivative of the wave function) are opposite at the location $$x$$. This behavior leads to the oscillation of the wave function in the classically allowed region. In the classically forbidden region, the wave function and its curvature always have the same sign (both positive or both negative at the location $$x$$).


text:
# Visual interpretation, on the Bloch sphere, when Hadamard gate is applied twice

It's known that the Hadamard operation is just a rotation of the sphere about the $\hat{y}$ axis by 90 degrees, followed by a rotation about the $\hat{x}$ axis by 180 degrees.

On the other hand, $H^{2}=I$, where $H$ is the unitary matrix corresponding to the Hadamard gate and $I$ is the identity matrix.

If we do the rotation corresponding to the Hadamard matrix twice, then based on $H^{2}=I$, we would come out to the original situation, right? But, somehow, I can not see that. Could someone shed some light on this problem?

• It should both be 90 degrees (about the y and x axis), right? Apr 6 '20 at 18:18

Here I give some additional analysis to Craig Gidneys answer. The Hadamard gate indeed can be subdivided into two individual rotations, as suggested in the initial question. However, every single qubit gate can also be described by a single rotation on the Bloch sphere. For the Hadamard gate, this is a rotation around the axis (rho, elev, azim) = $$(1, \frac{\pi}{4}, 0)$$. The rotation axis is drawn as a black arrow in the image.

Shown is the evolution of the initial state $$|0\rangle$$ during two sequentially applied Hadamard gates. The red state vectors show the evolution during the first Hadamard gate, transferring state $$|0\rangle$$ to state $$|x\rangle$$ (in the image only x). The blue state vectors then show the evolution during the second Hadamard gate, transferring state $$|x\rangle$$ back to state $$|0\rangle$$. This geometric representation shows for one exemplary initial state, why $$H^2 = I$$.

The image can be resimulated with python and the toolbox qutip.

from qutip import *
import numpy as np
import scipy
import matplotlib.colors
import scipy

#the gate
# the hamilton operator describing the evolution during the hadamard gate

#create initial state vector
psi0 = (basis(2, 0)).unit()

# describing the gate as time evolution
def gate(t):
return (-2*np.pi*1.j*hamilton*t).expm()

# hadamard gate for t = 0.5
# In[1]: gate(0.5)
# Out[3]:
# Quantum object: dims = [[2], [2]], shape = (2, 2), type = oper, isherm = True
# Qobj data =
# [[ 0.70710678  0.70710678]
#  [ 0.70710678 -0.70710678]]

# evolve the gate
n = 25
psi = [gate(t)*psi0 for t in np.linspace(0, 1., 2*n)]

# plotting the states. State evolution during the first hamadard gate is red. During second hadamard gate is blue
b = Bloch()
b.vector_color = [matplotlib.colors.to_rgba('r', alpha=i) for i in np.arange(n)/float(n)] + [matplotlib.colors.to_rgba('b', alpha=i) for i in np.arange(n)/float(n)]  + ['black']

b.show()

The Hadamard operation is a 180 degree rotation around the diagonal X+Z axis of the Bloch sphere.

A 180-degree rotation around X+Z swaps points on the X axis to the Z axis (and vice versa), and negates points on the Y axis. The same thing is true of rotating 90 degrees around Y then 180 degrees around X.

Note that quantum operations have a global phase in addition to the rotation part, so whether you get an exact equality between the operation matrices will depend on that. For example, $X \cdot Y^{1/2} = H \cdot \sqrt{i}$ instead of just $H$. Global phase only matters if you start applying the operation conditional on other qubits.

It can be nice to represent things geometrically. We can represent qubits using vectors, as I'm sure you know. So let's start with a qubit in the $|0\rangle$ state, or in the state $\begin{bmatrix}1\\0\end{bmatrix}$. We can graph this as

(That blue there is the vector representing the qubit.) So, now that we have our initial state, let's apply the Hadamard gate to it. The Hadamard gate is represented by $\frac{1}{\sqrt{2}}\begin{bmatrix}1&1\\1&-1\end{bmatrix}$. When we multiply the vector $\begin{bmatrix}1\\0\end{bmatrix}$ and the above matrix, we get the Hadamard gate applied to the zero state, or $\begin{bmatrix}\frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}}\end{bmatrix}$. Graphing that, we get

Now, let's apply the Hadamard gate again. We have our vector $\begin{bmatrix}\frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}}\end{bmatrix}$ and the matrix representing the Hadamard gate, which we can rewrite as $\begin{bmatrix}\frac{1}{\sqrt{2}}&\frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}}&-\frac{1}{\sqrt{2}}\end{bmatrix}$ for simplicity. Now to multiply the two, of course, we do $\frac{1}{\sqrt{2}}\cdot\begin{bmatrix}\frac{1}{\sqrt{2}}\\\frac{1}{\sqrt{2}}\end{bmatrix}+\frac{1}{\sqrt{2}}\cdot\begin{bmatrix}\frac{1}{\sqrt{2}}\\-\frac{1}{\sqrt{2}}\end{bmatrix}$. $\sqrt{2}^2$ is of course $2$, so we get $\begin{bmatrix}\frac{1}{2}\\\frac{1}{2}\end{bmatrix}+\begin{bmatrix}\frac{1}{2}\\-\frac{1}{2}\end{bmatrix}$. This comes out to $\begin{bmatrix}1\\0\end{bmatrix}$, and the graph at the beginning. We're back where we started!

Hopefully this helps; if it doesn't, let me know and I'll try to think up another way to picture it.

• thank you for your explanation. I understand that $H^{2}=I$. My question is more related to the Bloch sphere representation of the Hadamard matrix. I do not understand that why do the Hadamard-matrix- rotation twice (rotate the sphere about the y axis by 90 degree, then about the x axis by 180 degree, then about the y axis by 90 degree, and then in the end, about the x axis by 180 degree), would return the sphere to the original position? Thank you a lot. Feb 27 '17 at 22:38

Before starting I should mention I am using Craig Gidney's tool and some screenshots from it, quirk, which is definitely worths to be checked as himself also has left an answer here, now here is my understanding:

Lets start with some initial state on quirk so we can have an illustrative perception on whats going on:

This is just some random qubit state I've made using combination of three gates. What happens if we apply Hadamard to this?

Well this is combination of "rotation of the sphere about the $\hat{y}$ axis by 90 degrees, followed by a rotation about the $\hat{x}$ axis by 180 degrees" but lets tears this apart using available simpler gates and the definition your are interested:

Identical to applying Hadamard gate itself, we applied $Y^½$ then X. It may not be obvious how we reached from our input to this, so have at look at Y rotation animation and X rotation at quirk. Before continuing having look at these also would be useful I guess:

X rotation      Y rotation      Z rotation

Now I guess here is the interesting part, if we apply $Y^½$ again we will reach to this:

But what does this mean? This is equal to X rotation of the input state:

With all these preparations I guess this is the point, if you rotate a sphere 180 degree just by an axis, equal rotations on other axises before and after first rotation will cancel each out and all you need to reach to the initial state is to apply the first axis 180 degree rotation again, just like double applying Hadamard.

In a sense it is like doing rotation against an actual mirror, on the global coordination the real rotation is different from the rotation happening on the mirror (in here $Y^½$ gate) but there is only one reality. Trying rotating an actual ball against a mirror can help to the understanding :)

And of course this is after applying two Hadamard consequently which is equal to the our initial state:

Here is the quirk's model I've prepared for this answer and can be used and tweaked for getting better understanding.

At the end, I should mention that Hadamard itself can be written as a one step 3d rotation, something like rotate(pi/2, 0, pi) but one step 3d rotations are less intuitive I guess and two step one axis rotation are easier to understand that's why you've found that quote and it is perhaps better to describe it in this way.


text:
# 009C Sample Final 2

This is a sample, and is meant to represent the material usually covered in Math 9C for the final. An actual test may or may not be similar.

Click on the  boxed problem numbers  to go to a solution.

## Problem 1

Test if the following sequences converge or diverge. Also find the limit of each convergent sequence.

(a)  ${\displaystyle a_{n}={\frac {\ln(n)}{\ln(n+1)}}}$

(b)  ${\displaystyle a_{n}={\bigg (}{\frac {n}{n+1}}{\bigg )}^{n}}$

## Problem 2

For each of the following series, find the sum if it converges. If it diverges, explain why.

(a)  ${\displaystyle 4-2+1-{\frac {1}{2}}+{\frac {1}{4}}-{\frac {1}{8}}+\cdots }$

(b)  ${\displaystyle \sum _{n=1}^{\infty }{\frac {1}{(2n-1)(2n+1)}}}$

## Problem 3

Determine if the following series converges or diverges. Please give your reason(s).

(a)  ${\displaystyle \sum _{n=0}^{\infty }{\frac {n!}{(2n)!}}}$

(b)  ${\displaystyle \sum _{n=0}^{\infty }(-1)^{n}{\frac {1}{n+1}}}$

## Problem 4

(a) Find the radius of convergence for the power series

${\displaystyle \sum _{n=1}^{\infty }(-1)^{n}{\frac {x^{n}}{n}}.}$

(b) Find the interval of convergence of the above series.

## Problem 5

Find the Taylor Polynomials of order 0, 1, 2, 3 generated by  ${\displaystyle f(x)=\cos(x)}$  at  ${\displaystyle x={\frac {\pi }{4}}.}$

## Problem 6

(a) Express the indefinite integral  ${\displaystyle \int \sin(x^{2})~dx}$  as a power series.

(b) Express the definite integral  ${\displaystyle \int _{0}^{1}\sin(x^{2})~dx}$  as a number series.

## Problem 7

(a) Consider the function  ${\displaystyle f(x)={\bigg (}1-{\frac {1}{2}}x{\bigg )}^{-2}.}$  Find the first three terms of its Binomial Series.

(b) Find its radius of convergence.

## Problem 8

Find  ${\displaystyle n}$  such that the Maclaurin polynomial of degree  ${\displaystyle n}$  of  ${\displaystyle f(x)=\cos(x)}$  approximates  ${\displaystyle \cos {\frac {\pi }{3}}}$  within 0.0001 of the actual value.

## Problem 9

A curve is given in polar coordinates by

${\displaystyle r=\sin(2\theta ).}$

(a) Sketch the curve.

(b) Compute  ${\displaystyle y'={\frac {dy}{dx}}.}$

(c) Compute  ${\displaystyle y''={\frac {d^{2}y}{dx^{2}}}.}$

## Problem 10

Find the length of the curve given by

${\displaystyle x=t^{2}}$
${\displaystyle y=t^{3}}$
${\displaystyle 0\leq t\leq 2}$