List of top conferences named "Symposium"

Some people occasionally judge the quality of international conferences based on their names, saying that "symposium"s are not as proper as "conference"s. I heard that it is the case in some areas of study, but it is definitely not true in research areas I've been involved in and nearby fields.

So, here I list up top international conferences that have "symposium" on their names, so that I can give the list when someone says the same thing in the future. The list only shows real top conferences, but not top-ish ones.

Operating Systems / System Software
- ACM Symposium on Operating Systems Principles (SOSP)
- USENIX Symposium on Operating Systems Design and Implementation (OSDI)
- USENIX Symposium on Networked Systems Design and Implementation (NSDI)
Parallel Computing
- ACM Symposium on High-Performance Parallel and Distributed Computing (HPDC)
- IEEE International Parallel & Distributed Processing Symposium (IPDPS)
Computer Architecture
- IEEE/ACM International Symposium on Microarchitecture (Micro)
- International Symposium on Computer Architecture (ISCA)
- IEEE International Symposium on High-Performance Computer Architecture (HPCA)
Programming Language
- ACM SIGPLAN Symposium on Principles of Programming Languages (POPL)
Security
- IEEE Symposium on Security and Privacy (IEEE S&P)
- USENIX Security Symposium (USENIX Security)

A side note for those who have never heard of "USENIX"; it is an academic organization that hosts international conferences and related events (like ACM and IEEE) especially for the operating systems and system software fields. It is considered as a highly reliable organization and the conferences it hosts are normally very high quality.

2018-12-24

Deciding the probability of a coin to show its head from the expected number of heads for N tosses

A couple of weeks ago I hit a small math problem related to probabilistic and I thought it was trival (it took me a few hours to solve, though :p ). However I could not find a good stack exchange post or whatever that answers my problem, so I put it here for the sake of my future reference and possibly some people who happen to hit the same problem.

Note that the "short answer" itself really is short and trival, but the point of this post is the last section that describes the relationship between the "short" and the "long" answers.

Problem Definition

Let the probability that a coin shows its head in a coin toss be x (0 < x < 1) and the expected number of heads after N tosses be M, compute x using N and M.

Short Answer

The expected number of heads for one toss is obvisouly x. Because the expected value of the sum of two independent probablistic variables is equal to the sum of the expected value of each probablistic variable (E[X + Y] = E[X] + E[Y]), the expected number of heads for N tosses is Nx.

Therefore, $M = Nx$ and $x = \frac{M}{N}$ .

Long Answer (kind of)

By definition, the expected number of heads M can be expressed using x and N as follows:

${ \displaystyle M = \sum_{n=1}^{N} ( n \times p(n) ) }$

where $p(n)$ is the probability that exactly n coins show their heads and defined as:

${ \displaystyle p(n) \\ = C(N,n) \times x^{n}(1-x)^{N-n} \\ = \frac{N!}{n!(N-n)!} \times x^{n}(1-x)^{N-n} }$

Therefore,

${ \displaystyle M = \sum_{n=1}^{N} \Bigl( n \times \frac{N!}{n!(N-n)!} \times x^{n}(1-x)^{N-n} \Bigr) }$

We can compute x from M and N by solving this equation for x..... but how??? (this is an N-th order equation of x!)

What's Behind

Both the short and the long answers say correct stuff, which means one thing:

${ \displaystyle \sum_{n=1}^{N} \Bigl( n \times \frac{N!}{n!(N-n)!} \times x^{n}(1-x)^{N-n} \Bigr) = Nx }$

And below is a proof:

${ \displaystyle \sum_{n=1}^{N} \Bigl( n \times \frac{N!}{n!(N-n)!} \times x^{n}(1-x)^{N-n} \Bigr) }$

${ \displaystyle = Nx \times \sum_{n=1}^{N} \frac{(N-1)!}{(n-1)!(N-n)!} x^{n-1}(1-x)^{N-n} }$

${ \displaystyle = Nx \times \sum_{k=0}^{K} \frac{K!}{k!(K-k)!} x^{k}(1-x)^{K-k} }$

where $n-1 = k$ and $N-1 = K$ . Note that $N-n = (N-1) - (n-1) = K-k$ . The term after $Nx$ is equal to 1 as shown below:

${ \displaystyle \sum_{k=0}^{K} \frac{K!}{k!(K-k)!} x^{k}(1-x)^{K-k} }$

${ \displaystyle = \sum_{k=0}^{K} \Bigl( C(K, k) \times x^{k}(1-x)^{K-k} \Bigr) \\ = (x + (1-x))^{K} \\ = 1 }$

Let's Check Numerically

For those who may suspect the proof above, here are Ms calculated by the short and the long answers for N = 100 (there are small differences by numerical errors, but they are pretty much the same).

x	M_short	M_long
0.0	0.0	0.0
0.04	4.0	3.9999999999999862
0.08	8.0	8.000000000000032
0.12	12.0	11.999999999999998
0.16	16.0	15.99999999999996
0.2	20.0	20.00000000000012
0.24	24.0	23.999999999999993
0.28	28.000000000000004	28.0
0.32	32.0	31.99999999999981
0.36	36.0	35.99999999999999
0.4	40.0	39.99999999999999
0.44	44.0	44.00000000000023
0.48	48.0	47.99999999999998
0.52	52.0	52.0
0.56	56.00000000000001	56.00000000000001
0.6	60.0	59.99999999999997
0.64	64.0	64.0
0.68	68.0	68.0
0.72	72.0	71.99999999999999
0.76	76.0	75.99999999999997
0.8	80.0	80.0
0.84	84.0	84.00000000000001
0.88	88.0	88.00000000000001
0.92	92.0	92.00000000000001
0.96	96.0	96.0

Here is the code used to generate the table above. Note that M_long(x) does not work for a large N due to overflow.

import scipy.special as sp

N = 100

def M_short(x):
    return N * x

def M_long(x):
    ans = 0
    for n in range(1, N+1):
        ans += n * sp.comb(N, n) * pow(x, n) * pow(1 - x, N-n)
    return ans

print("|x|M_short|M_long|")
print("|-|-------|------|")
for i in range(0, 25):
    x = i / 25
    print("|", x, "|", M_short(x), "|" , M_long(x), "|")

2018-11-13

IPSJ accepted to delete my sex info from their membership DB

Information Processing Society of Japan (IPSJ) is what they claim the largest academic organization related to Informatics in Japan. I've been a member of it since 2009 when I was a 4th year undergrad student, I've participated in many domestic workshops and events they host, and I've received a few awards from them.

One thing I was concerned about them, is that they require to register one's sex (choosing either from man or woman) along with one's name and afflication and other information when someone joins IPSJ.

Because I wanted to choose a third option "prefer not to answer" (which I believe must be choosable) due to two reasons below, I asked them to add it to the sex column of the registration form.

Reason 1: I cannot imagine a single reason to require registering one's sex to receive their membership service.
Reason 2: Registering your sex is not only like you declare you have a particular gene, but it makes people see you with largely stereotyped ways.

I actually didn't expect a positive answer, because as an IT person I know that modifying even a single bit of an enterprise system costs tremendous amount of money and time (like 100s of 1000s of dollars, literally).

Turned out, my expectation was wrong in a good way. Their response was that they deleted my sex information from their membership DB and they also said that they would conisider adding a new option ("prefer not to answer") in the future. It was very nice of them to have (halfway) accepted my request, and I belive they will do the right thing in near future.

Figure: a screenshot of my membership info in their portal. The sex ("性別") column is blank. f:id:sorami_chi:20181113005533j:plain

2018-07-03

Ochanomizu University to accept non-women

Ochanomizu University to accept non-women who recognize themselves as female in addition to any women (including ones recognizing themselves as male and neutral). I think it's a very large step, and I want them to keep going but not stop here.

Note for those who are not familiar with Japanese universities: it used to be a women-only university but will introduce a new policy from next year.

In the short term, it is strongly needed to support students accepted by the new policy not only in the school but also around it. Do all apartment owners accept these students? I don't think so. Do all stations in Tokyo have universal restrooms? No they don't. I hope this new policy will have an impact to the society around the school as well.

In the long term, I believe now in this information era is the time to re-consider the long established concept of male vs. female. Why do we need to distinguish the two and map every single person to either of them? Why should the biological differences spiritually affect the way of thinking? How can we find a compromise in the real world where some do not wanna be distinguished (not discriminated) but others do feel comfortable being categorized? I hope this new policy will be a trigger to initiate constructive discussions, but not meaningless quarrels as usually seen in equality-related stuff.

2018-05-06

Public Walfare (for the Constitution Memorial Day of Japan)

The Japanese constitution has several clauses that have the phrase "for the public welfare" in them. Basically what it says is that the fundamental human rights are respected if (and only if) they do not conflict with the "public welfare".

I have been long thinking that this "public welfare" is too vague so that it can be used to condemn almost anything, because there is actually no definition in the constitution. The vagueness may not be a problem if the people are culturally, religiously, morally and biologically "uniform", but obviously it is not the case. In an extreme case, if say 99% of people think that something is ugly, then that thing can be criminalized in order to promote the public welfare (people actually claim that things they hate must be criminalized and they often cite public welfare, although making something really criminalized is rarely done in my understanding).

It turned out that, this vagueness has actually been pointed out by the United Nations as well. The International Covenant on Civil and Political Rights of the United Nations had a 'concern that the concept of "public welfare" is vague and open-ended' (page 8 of http://tbinternet.ohchr.org/_layouts/treatybodyexternal/Download.aspx?symbolno=CCPR/C/JPN/CO/6&Lang=En ). There is a very good read (in Japanese) written by a professor of Osaka Sangyo University.

I guess there are two issues about this. First, people really do not care about it because for the majority of people who share the same way of thinking, something against the public welfare is what they do not want. So, condemning something against the public welfare is actually good for them! It might be the case that people do not even notice that the phrase "public welfare" is vague. Second, having a constructive and objective discussion on how to change the constitution is very difficult in Japan, because people are paranoid about the Clause No. 9 that says about the wars and forces (and I am too).

2018-02-18

'who am i' does not work in recent GNOME-terminal (and MATE-terminal)

The 'who am i' idiom and the problem

The *unix command who is used to "show who is logged on" (c.f. https://linux.die.net/man/1/who ), and who am i, which is equivalent to who -m, is an idiomatic usage of who that only shows the user who calls this command. So it tells who you are. A funny thing is that any string works as the arguments. The command only checks if the number of arguments is 2 and then executes who -m if it is. Thus, as the manual says, who mother loves yields the same result.

The problem is that it does not work in recent GNOME-terminal, MATE-terminal, and any other terminal emulators that rely on libvte. In these terminal emulators, who am i just returns nothing. I think this is a critical issue as who am i is used in many shell scripts to retrieve the current user name.

f:id:sorami_chi:20180217231615p:plain

How it is implemented

Before explaining why it doesn't work, I describe how it is implemented. The who.c file of gnu coreutils relies on the file named /var/run/utmp. This file contains login logs of the system and what who.c does is basically just opens the file, parse it and print the log entries.

In each entry of /var/run/utmp, a username and login information of that user are recorded such as the pid of the login process and the device name of the terminal the user is associated with (see the manual for the details). who am i compares the terminal device name in an entry with a string obtained by ttyname(3), and prints the entry if they match.

  if (my_line_only) // when -m is specified
    {
      // retrieves the device name of stdin
      ttyname_b = ttyname (STDIN_FILENO);
      ...
    }

  while (n--) // for each entry of /var/run/utmp
    {
      // if -m is not specified, or
      // the device name of stdin is equal to the device name of the terminal associated with this user
      if (!my_line_only
          || STREQ_LEN (ttyname_b, utmp_buf->ut_line,
                        sizeof (utmp_buf->ut_line)))
        {
        // parse and print the entry
        ...
        }

Code: A part of who.c of gnu coreutils (comments are added by me)

Why it doesn't work and what to do

The root cause behind this problem is that /var/run/utmp is not magically maintained by the OS and it has to be updated by each process, while recent versions of libvte does not do this. This is not a bug of libvte, but an intentional choice discussed like here. Although in the same thread a concern about who am i was raised, it was just removed to improve the code cleanness (it seems like the function to update /var/run/utmp was in a very nasty file that is almost never used). Because both GNOME-terminal and MATE-terminal use libvte, this problem exist in both of them.

Two easy alternatives are (1) to use xterm, which does not rely on libvte and updates /ver/run/tmp by itself, and (2) to use the whoami command, which uses a different mechanism, instead of who am i.

2018-01-01

キューブ型PC（SX58H7）のCPUとファン交換

以前知り合いがいらないからともらったキューブ型PCのCPUに負荷をかけまくっていると非常にうるさい＆性能が微妙に不満なので、CPUとファンを交換した。

基本的には Shuttle 社の SX58H7 というもの（これ）で、ただしベアボーンなので実際にどこのメーカーがCPUなどを組み込んで売ったのかは謎。キューブということで普通にバラして部品を交換できるか微妙だったが、あけてみるとちゃんと自分でバラせるようになっていた。（ベアボーンなのでバラせて当然？）

f:id:sorami_chi:20180102011018j:plain 外観。光学ドライブのフタが壊れている。

元々ついていた Core i7 920 はなんとSandy Bridgeより以前の世代でIntelの用語では「過去のプロセッサ・ファミリー」と呼ばれているが、やらせたい仕事がフェッチするデータ量が少なくかつconditional branchもあんまりない（と思う）という純粋に力勝負的なワークロードなので少しアップグレードすればまだまだいけると判断した。

ファンは一つしかなく、CPUから伸びたヒートシンクに風をあてて温まった空気を外に排気するという方式だった。Shuttle社公式の組み立て説明動画ではヒートシンク等のCPUまわりは6分ちょうどあたりから出てくる。なお動画ではヒートシンクとファンが合体して見えるが、これは実は別々になっていてファンを交換するだけなら本体後ろのネジをはずすだけで交換できる。

f:id:sorami_chi:20180102011015j:plain ケースをあけたところ。左の横向きについているファンでヒートシンクから来た熱を外に出す。その手前はグラボで特に必要ないがネジ山がつぶれてはずせなくなってしまった。

ついていた超うるさいファンは AD0912UX-A7BGL という型番のもので、どうやらこれがイマイチらしい。米アマゾンのレビューでも "it sounds like a Pentium 4 case fan" とか "sounds like a meat grinder" とか書かれている（meat grinderはなんかソーセージを作ったりするのに使う肉粉砕マシーン？？）。交換先のファンは GELID 社の Silent 9 というものにした。日本ではサイズ社が輸入して販売しているっぽい。アキバで1000円くらいで売っていた。気にしたポイントはPWMで回転数が制御できるものであることと、なんか静音っぽい製品であること。本当は羽の数とか回転数とかを見たほうがいいんだろうけど、ファンのことはあまりよくわからないので感で決めた。元々のものは 90mm でこれは 92mm と書いてあるけど、90mm と 92mm のファンは実際は同じ大きさらしく（？）、ベアボーンの部品であるファンを囲うアルミフレームに問題なく設置できた。

次にCPUだが、やらせたい仕事が純粋CPU勝負かついくらでも並列化できる（weak scalingできる）タスクなのでなるべく周波数が高い＆コア数が多いものが有利である。元々ついていたCPUと同じソケット（LGA1366）にささる中で一番コア数が多いのは Xeon X5690 で、周波数も十分高いので理想的にはこのCPUがよい。ただしXeon系CPUはあまり中古で出回っていないこと、元々ついていたCore i7 920よりマイクロアーキテクチャが1世代進んでいるのでBIOSを更新しないといけないかもしれない（かつベアボーン自体が古いのでもう新しいBIOSをダウンロードできないかもしれない）ことが微妙なポイントだった。

結局アキバの中古を扱う店で売っていた Core i7 965 Extreme Edition を購入した（Xeonは案の定売ってなかった）。歳末特価ということで（購入したのは12/31）、4900円で買えた。ヤフオクでは6500円程度で落札されているっぽいのでかなりオトクだった。なお発売当時の価格は $990 だった模様。実は中古のCPUを買ったのははじめてだけど、CPUはストレージや電源ユニットと違い冷却ミスで燃えない限りほぼ壊れないのでちょっと前の世代のCPUを中古で買うのが一番コスパがいいかもしれないと感じた（特に自宅で使っていてHWトランザクショナルメモリとか Cache Allocation Technology とかの新しいハードウェア機能がいらない場合）。あとはめっちゃ安いグリスを購入して終了。グリスの違いは自分で試したことがないのでよく分からない。

CPUの交換時にソケットのピンをちょっとひっかいた気がして不安だったが（LGA1366はCPU側ではなくソケット側にピンがある）、組み直してちゃんと起動できた。ヒートシンクがばっちり熱くなっているのでグリスは安物でOKだった模様。たぶんファンの回転数が元々のものより低くなっていて、音は静かになったが冷却性能はかなりギリギリな感じがある。冬はいいけど真夏は最大負荷で常用するのは無理かも知れない。その代わり音は劇的に静かになって、最大回転数の一段階手間までは隣りにあるNASのHDD動作音にかき消されてわからないレベルになった。最大回転数だと少し音が聞こえるが、まったくうるさいという感じではない。

一番問題のワークロードの性能は16%強改善された。コア数、キャッシュサイズ、マイクロアーキテクチャは元々のCPUと一緒なので純粋に周波数が上がったことによる効果である。なお今回はワークロードが完全に100%CPU勝負だと分かっているからの判断であり、一般にはメモリの性能（帯域、レイテンシ）もかなり効いてくるので周波数の比較だけで性能を議論するのは実はほとんど意味がない場合が多い。また搭載しているコアが数世代違うマシンの周波数だけを比べるのは現代と100年前の幸福度を給与の額面で比べるくらい意味がない。

Soramichi's blog

Some seek complex solutions to simple problems; it is better to find simple solutions to complex problems