\documentclass[a4paper, twocolumn,10pt]{jarticle}

\usepackage{fancyvrb}
\usepackage[chukan]{sotsuron}
\usepackage[dvips]{graphicx}

\addtolength{\oddsidemargin}{-40pt}

\renewcommand{\baselinestretch}{1.1}

\begin{document}


\twocolumn[
\fbox{
\begin{tabular}{lr}
��w�@�֍u�z�z���� & ����19�N1��12��\\
\multicolumn{2}{c}{{\Large \textbf{���U�^�X�N�X�P�W�����[�̌�������}}}\\
\multicolumn{2}{c}{{\Large \textbf{A Survey of Distributed Task Scheduler}}}\\
�ߎR�E�c�Y������ \hspace{80mm} & �d�q���w��U�@�C�m�P�N 56428 ����~�d\\
\end{tabular}
}
\vspace{5mm}
]

\setcounter{page}{1}

\section*{Abstract}

A grid environment offers vast computing resources, and it is used not only for numerical computations but also for data mining and natural language processing. For these data-intensive applications, distributed task scheduler offers useful environment. However, it is not easy to develop a smart scheduler which considers data locality and task dependencies. 

This survey shows some exsiting scheduling algorithms and new researches which focus on dependency and data intensive conditions. A simple min-min heuristics performs well to schedule tasks without dependencies. To schedule data intensive tasks with dependencies, the makespan was halved by co-scheduling tasks and replicas with GA in a simulation.


\section{�͂��߂�}

�O���b�h���́A��ʂ̊��ł͖]�߂Ȃ�����Ȍv�Z������񋟂���B
���[�U�[�͑�����CPU�ɂ��v�Z�́A�L��ȃ�������ԂƁA�f�B�X�N�̈��p���邱�Ƃ��o����̂ŁA�]���s�����Ƃ��o���Ȃ�������K�͂ȏ������s�����Ƃ��o����B

����ŁA����A�v���P�[�V�����͈�ʂ̃v���O���}�ɂƂ��ē���݂̂�����̂ł͂Ȃ��A��ʂɋL�q�͓���B����ɉ����āA�O���b�h���̓m�[�h���\�E�A�[�L�e�N�`���[���s�ώ��ł����ɁA�l�b�g���[�N�I�Ƀ��C�e���V���ɒ[�ɑ傫���m�[�h�A�o���h�����������m�[�h���܂ނ��Ƃ��������Ȃ��B���̂��ߊe�m�[�h�̓������l�������Ƀv���O���������s����ƁA���\���ቺ���Ă��܂��B%����A�ݒ�ɑ���Ȏ��Ԃ�v���Ă��܂��B

�v���O�����̕��񉻂��l����ہA��ʂɖ��ȒʐM���K�v�ȃA�v���P�[�V�����ł́A��p�̕���A���S���Y�����J�����邱�Ƃ��s���ł���B����A���S���Y���ł́A�����v���O�����ƈقȂ�A�v���O�����͕����̃X���b�h�ɂ���ĕ���Ɏ��s�����B�܂��A�K�v�ɂȂ�f�[�^�����ꂽ�v���Z�b�T�ɑ��݂���ꍇ�́A���b�Z�[�W�p�b�V���O�⋤�L��������p���ē]������K�v������B�ʐM�͒ʏ�̃������A�N�Z�X�ɔ�ׂĒx�����߁A�����v���O�����Ƃ͈قȂ����f�[�^�A�N�Z�X�̍H�v���K�v�ɂȂ�B
�܂��A���ɃO���b�h���͊e�m�[�h���s�ώ��Ȃ̂ŁA���\�����}��ɂ́A�����L�̃`���[�j���O���K�v�ɂȂ�A�O���b�h�̐��\���\���ɔ�������A�v���P�[�V�����������̂͊ȒP�ł͂Ȃ��B

����ɑ΂��A�ߔN�d�v�x�������Ă���f�[�^�}�C�j���O�ⓝ�v�I�Ȏ��R���ꏈ���́A�����̋Ǐ������������̂������B���̂悤�ȃA�v���P�[�V�����ł́A����f�[�^�ɑ΂��ď������s���v���Z�b�T�́A���̃v���Z�b�T�ƕp�ɂɒʐM�����邱�ƂȂ��������s�����Ƃ��o����B���̂��߁A�\�߃f�[�^��K�؂ɕ������āA���ꂼ��̃m�[�h�Ńv���O�����𑖂点��΁A���G�ȕ���v���O�������������ƂȂ��Ɍ����I�ɃO���b�h���̐��\���g�����Ƃ��o����B

�O���b�h���ɂ����Ĉ�A�̃^�X�N�����s����~�h���E�F�A���A���U�^�X�N�X�P�W�����[�ƌĂԁB\cite{taxonomy}����́A��������̒����^�X�N���m�[�h�Ɋ���U��A���K�v�ȃt�@�C����K�X�]��������̂ł���B��{�I�ɂ̓^�X�N�����u�̃m�[�h�Ŏ��s���A�K�v�ɉ����ăt�@�C����]���ł���V�X�e��������΂悢���A��ʂɐ��\�����コ���邽�߂ɂ́A�����_���ł͂Ȃ������X�P�W���[�����O���s���K�v�����邱�Ƃ��m���Ă���B�܂���{�Ƃ��āA���\�������m�[�h�ɂ͑����̃^�X�N������U��A�Ⴂ�m�[�h�ɂ͏��Ȃ��^�X�N������U��B�܂��A����^�X�N�̏����ɕK�v�ȃt�@�C��������ꍇ�́A�Ȃ�ׂ����̃t�@�C�������݂���m�[�h�̋߂��Ɋ��蓖�Ă�B

���������s�ώ��Ȋ��ɂ�����X�P�W���[�����O�́A���ɑ����̌���������B�������A�ߔN�V���ɃX�P�W�����[�ɂ́A��̗v�������߂��Ă���B��̓��[�N�t���[�A������̓f�[�^�E�C���e���V�u�ȃA�v���P�[�V�����ł���B���[�N�t���[�͈ˑ������������^�X�N�̏W���ŁA�A�v���P�[�V�����L�q�̎��R�x����������ŁA
�^�X�N�̎��s�����ɂ���đS�̂̎��s���Ԃ��傫���ω�����B�܂��A����^�X�N�ɂ���Đ������ꂽ�f�[�^�𑼂̃^�X�N�����p���邽�߁A�X�P�W���[�����O�����G�ɂȂ�B�f�[�^�E�C���e���V�u�ȃA�v���P�[�V�����ł́A�f�[�^�̓]�����Ԃ��S�̂̏����ɑ΂��Đ�߂鎞�Ԃ��傫�Ȋ������߂�̂ŁA�����悭�f�[�^�]�����s���̂��s���ƂȂ�B

�{���\�ł́A�O���b�h���ɑ΂��ă^�X�N�𕪔z����X�P�W���[���ɂ��āA�����A���S���Y������������A���[�N�t���[��f�[�^�E�C���e���V�u�Ȋ��ɑΉ������������Љ��B


\section{���U�^�X�N�X�P�W�����[}

\subsection{��ʓI�ȗv��}

���U�^�X�N�X�P�W�����[�́A�^����ꂽ�^�X�N�Q���m�[�h�Ɋ��蓖�Ă�B���̂Ƃ��ɍl����������Ƃ��ẮA�ȉ��̓_����������B

\begin{itemize}
\item �m�[�h�����p�\���ǂ���
\item �m�[�h�̐��\�E���G�x
\item �^�X�N�̎��s�R�X�g (����)
\item �^�X�N�ɕK�v�ȃf�[�^
\item �^�X�N���s�ɕK�v�ȃf�[�^�̓]���R�X�g (����)
\end{itemize}

�����̏������l�����A�X�P�W���[�����O���s���B�^�X�N�̎��s���Ԃ�f�[�^�̓]���R�X�g�̓m�[�h�ɂ���ĈقȂ�A���������s�O�ɐ��m�ɂ͗\���o���Ȃ��ꍇ�������B���̂��ߎ��ۂ̃V�X�e���ł́A���p�ł���m�[�h�ɑ΂��A���̃m�[�h�Ń^�X�N�����s�\���ǂ����A�Ȃǂ̊ȒP�ȃ}�b�`���O���s�������Ń^�X�N������U���Ă������̂�����B���̂悤�ȃV�X�e���̗�Ƃ��Ă�Condor \cite{condor}����������B�������A�^�X�N�̎��s���Ԃ�t�@�C���̓]�����Ԃ�S���l�����Ȃ��ꍇ�A���\���傫���ቺ����\��������B

�v��I�Ƀ^�X�N�X�P�W���[�����O���s���ꍇ�A�ړI�֐���I������K�v������B����ɂ͓]���ʁE���G���̕��ω��ȂǗl�X�Ȃ��̂��l�����邪�A�����ł�makespan(��A�̃^�X�N�̏������J�n���Ă���S�^�X�N���I������܂ł̎���) ���ŏ���������̂ɂ��čl����B


\subsection{���[�N�t���[}

���[�N�t���[�Ƃ́A�����A�̃^�X�N���A�ˑ����ɉ����ăO���t�ŋL�q�������̂ł���A����������E�̏����̒��ۉ��Ƃ��ėp������B
��������E�J��Ԃ����܂ނ��́A�܂܂Ȃ����̂ȂǗl�X�ȋL�q�̕��@�����邪�A�����ł͏�������͎������ADAG (Directed acyclic graph)�ŕ\�������̂��l����B

���[�N�t���[�͒P���ȕ���^�X�N���s�ɔ�׍����L�q�͂����B�����ɂ͕K�v�s���Ȉˑ����݂̂��L�q����Ă���A��̓I�ȃm�[�h�̐���A�m�[�h�ɑ΂���^�X�N�̊���U�肪������Ă���킯�ł͂Ȃ��B���̂��߁A�X�P�W�����[�����s���ɗ��p�ł���m�[�h���E�l�b�g���[�N�̏󋵂Ȃǂɂ���āA���I�Ɍ����̗ǂ����s�������v�悷�邱�Ƃ��ł���B���[�U�[�͕���v���O���~���O�Ɋւ���[���m���������Ă��A�ȒP�ɃO���b�h���𗘗p���āA���G�ȑ�K�͂ȏ������s�����Ƃ��o����B���[�N�t���[�̃X�P�W�����[�Ƃ��ẮACondor�̃T�u�V�X�e���Ƃ��ė��p�ł���DAGman \cite{dagman}����������BDAGMan�̓^�X�N�Q��DAG��ǂݍ��݁A���s�\�ȃ^�X�N��Condor�ɓ�������B

DAGman�ł͍s���Ă��Ȃ����A%���[�N�t���[�S�̂𕪐͂��邱�ƂŁA�S�̂̏������Ԃ�啝�ɒZ�k�ł��邱�Ƃ��m���Ă���B
���[�N�t���[�𕪐͂��邱�Ƃɂ���āA����Ɏ��s�ł���^�X�N�E�o���Ȃ��^�X�N�����炩�ɂȂ�B�܂��A�S�̂̏����𑁂��I��点�邽�ߏd�v�ɂȂ�^�X�N��������΁A����𑁂߂Ɏ��s���邱�ƂŁA�S�̂̏������Ԃ�Z�k�ł���B

����ŁA��ʂɈˑ����̂���^�X�N�ł́A�O�̃^�X�N�ɂ���Đ������ꂽ���ԃf�[�^���K�v�ɂȂ邪�A���̃f�[�^�����������ꏊ�̓X�P�W���[���ɂ���ĕω�����B�܂��A���s�����̐��񂪂��邽�߁A���s�s�\�ȃX�P�W���[�����������꓾��B���̂��߁A�X�P�W���[�����O�̃A���S���Y����蕡�G�ɕK�v�ɂȂ��Ă��܂��B



\subsection{�f�[�^�E�C���e���V�u��}

�R���s���[�^�̐��\����A���ɋL���e�ʂ̔���I�ȑ����ɂ���āA����܂Ŗ]�߂Ȃ�������K�͂ȏ������\�ɂȂ��Ă���B
��Ƃ��ẮAWeb��̃h�L�������g�ɑ΂��錾�ꏈ���E��`�q��͂Ȃǂ���������B
�����͏������̂͒P���ł����Ă��A��K�͂ȃf�[�^�ɑ΂��ď������s�����ƂŁA����܂œ��邱�Ƃ��o���Ȃ��������ʂ��オ���Ă���B
�f�[�^�T�C�Y�̓e���o�C�g����y�^�o�C�g�ɒB���A���񏈗����s���ɂȂ��Ă���B

�O���b�h���ł��̂悤�ȃA�v���P�[�V�����������ꍇ�A�����̏����̓^�X�N�Ԃ̊֘A�����Ⴂ�̂ŁA�e�m�[�h�Ƀf�[�^�����܂��z�������Ό����I�Ɏ��s�ł������A�S�̂̎��s���Ԃɐ�߂�f�[�^�]�����Ԃ��傫���Ȃ�B���ɁA�O���b�h���ł̓��C�e���V���傫���A�o���h�����������l�b�g���[�N�����݂��邽�߁A�����I�ȃf�[�^�]���v��𗧂Ă邱�Ƃ��d�v�ɂȂ�B

�܂��A�f�[�^�]�������炷�悤�ȃX�P�W���[�����O���K�v�ɂȂ�B�^�X�N���s�ɕK�v�ȃf�[�^������m�[�h�ɂ���Ƃ��́A�\�Ȃ炻�̃m�[�h�Ŏ��s����ƁA�f�[�^�]�����s�v�ɂȂ�B�܂��A����^�X�N�̏o�͂���f�[�^�𗘗p����^�X�N����������ꍇ�́A���̃^�X�N�̓l�b�g���[�N�I�ɋ߂��m�[�h�������m�[�h�Ŏ��s���邱�Ƃ��]�܂����B

���ɁA�t�@�C�����v���J�̗��p����������B����́A�����̃m�[�h���K�v�Ƃ���t�@�C���͌����I�ɓ]�����邽�߂ɕK�v�ɂȂ��@�ŁA�f�[�^��\�߂������̑�\�I�ȃm�[�h�ɃR�s�[���Ă����A����m�[�h���̃t�@�C����K�v�ɂȂ����ۂ́A�߂��̃��v���J����R�s�[����Ƃ������̂ł���B�t�s��h���_�ł��A�����f�[�^�̓]���͉��x���s��Ȃ����Ƃ��]�܂����B

�Ō�ɁA���ԃt�@�C���̖�肪����B�O���b�h�̌v�Z�m�[�h�������[�J���f�B�X�N�́A���܂�傫���Ȃ��ꍇ�������B���̂悤�ȏꍇ�A����f�[�^��p����^�X�N���S�Ď��s����邩�A���̃f�[�^�����̃m�[�h�ɃR�s�[���ꂽ�ꍇ�A���̃f�[�^�͕K�v�ɉ����č폜�ł���B�t�Ɏ����I�ɍ폜����Ȃ��ꍇ�A�e�n�̃m�[�h�Ńf�B�X�N����������A�^�X�N�̎��s���s�\�ɂȂ��Ă��܂��B



\section{�X�P�W���[�����O�A���S���Y��}
��Q�̃m�[�h�Ɉ�Q�̃^�X�N�����蓖�Ă�����A�X�P�W���[�����O���ƌĂԁB
�m�[�h���s�ώ��ŁA����^�X�N����������̂ɂ����鎞�Ԃ��傫���قȂ�ꍇ�A�X�P�W���[���ɂ���đS�̂ł̏������Ԃ͑傫���ω�����B
�f�[�^�C���e���V�u�Ȗ��ł́A����^�X�N�̎��s���Ԃ́A�K�v�ȃf�[�^��]������K�v���Ȃ��ꍇ�E�߂��ɓ]������ꍇ�E�����ɓ]������ꍇ��
�܂��^�X�N�ԂɈˑ���������ꍇ�́A�ǂ̃^�X�N��D��I�ɏ������邩����؂Ȑ�������ɂȂ�B

�s�ώ��Ȋ����ł̃X�P�W���[�����O�͐V�������ł͂Ȃ��A����܂łɗl�X�ȃA���S���Y������Ă���Ă���B
����܂ł͊e�m�[�h�̌v�Z�\�͂��Ⴉ�����̂ŁA���I�Ɍv��ł��A�v�Z�R�X�g���������X�P�W���[�����O�A���S���Y������Ă���Ă����B
�������A�ߔN�̐��\����ɂ��AGA�̂悤�ȑ傫�Ȍv�Z�ʂ�K�v�Ƃ���X�P�W���[�����O�A���S���Y�������ۓI�ɂȂ����B

�ȍ~�A�P�������ꂽ���f���ɂ����āA�������̃X�P�W���[�����O���f�����������B
�����ŗp������T�O�ɁAETC�s�� (estimation time of completion)�Ƃ������̂�����B����́A�X�P�W���[���\�ȑS�Ẵ^�X�N�ɂ��āA�e�m�[�h�ŏ��������ꍇ�A�����I���܂łɂǂꂾ���̎��Ԃ������邩���������̂ł���B���̎��Ԃ́A�ȉ��̎O�̗v�f�����v���ċ��߂�B

\begin{itemize}
\item �m�[�h�����p�\�ɂȂ�܂ł̎���
\item �t�@�C���]������
\item �^�X�N���s����
\end{itemize}

�t�@�C���]�����Ԃ́A�f�[�^�T�C�Y�ƃo���h�����琄�肷��B�����̏ꍇ�A�l�b�g���[�N���t�s�͍l������Ă��Ȃ��B
�^�X�N���s���Ԃ��A���ۂ̃A�v���P�[�V�����̋������琄�����ꂽ��A�܂����[�U�[�������I�Ɏw�肵���肷��B

ETC�s��̑����Ƃ��āAconsistency�Ƃ������̂�����B����^�X�N$t_{0}$�̏������Ԃ��m�[�h$n_{0}$�ƃm�[�h$n_{1}$�Ŕ�r�����ꍇ�A$n_{0}$�̕����������Ԃ��Z�������ꍇ�A������^�X�N�ɂ���$n_{0}$�ɂ�鏈�����Ԃ�$n_{1}$�ɂ�鏈�����Ԃ��Z���Ȃ�Ƃ��AETC�s���consistent�ł���Ƃ����B��ʂɑ傫�ȃf�[�^��K�v�Ƃ��Ȃ��A�v�Z�����C���̃A�v���P�[�V�����ł́AETC�͒P���Ƀv���Z�b�T�̑��x�ɔ���Ⴗ�邽�߁Aconsistent�ɂȂ�B
���̂悤�ȏ������ł́A�ǂ��X�P�W���[���ƈ����X�P�W���[���̍����������̂ŁA�����_���ȃX�P�W���[�����O�ł��S�̂̏������Ԃ����܂舫�����Ȃ����Ƃ��m���Ă���B
����ɑ΂��A�^�X�N�ɂ���ăm�[�h���Ƃ̏������Ԃ̒��Z���قȂ�ꍇ��inconsistent�ƌĂԁB��ʂɃ^�X�N�ɕK�v�Ƃ����f�[�^���e�n�ɕ��U���Ă���ꍇ�A�^�X�N�������ԂɊ܂܂��f�[�^�]�����Ԃ̓m�[�h�ɂ���đ傫���قȂ�̂ŁAETC�s���inconsistent�ɂȂ�B�����_���ȃX�P�W���[�����O��Inconsistent�ȃ^�X�N�Q���X�P�W���[�����O����ƁA�������Ԃ��傫�����тĂ��܂��B


\subsection{Greedy�ȃX�P�W���[�����O}
�X�P�W���[�����O�ɂ����āA�ÓT�I�ɗǂ����ʂ�������@�Ƃ��āA�~����@(Greedy algorithm)��p�����@����Ă���Ă���B�����́A�^�X�N���S���X�P�W���[������Ă��Ȃ���Ԃ���o�����A��X�e�b�v�ɂ���̃^�X�N������U���āA�ŏI�I�Ɋ��S�ȃX�P�W���[���𐶐�����B

�܂��A�ŏ��̏�Ԃɂ�����ETC�s�񂪐��������B����ETC�s�񂪌v�Z���ꂽ��A���ɂǂ̃^�X�N��D��I�ɃX�P�W���[�����邩�����肷��B�D�悳���^�X�N�̑I�ѕ��Ƃ��āA�����ł�Max-min�EMin-min�Esufferage�̎O��@���������B

Max-min, Min-min�ɂ����ẮA�e�^�X�N�ɂ��āA�ŏ��̊������Ԃ�I������B��������ɁA�ł�������������������^�X�N��I������̂�Min-min�Ƃ�����@�ŁA�ł��x����������������^�X�N��I������̂�Max-min�ł���BMin-min�͌y���^�X�N���D��I�ɃX�P�W���[�����O����AMax-min�ł͏d���^�X�N���D��I�ɃX�P�W���[�������B

�������sufferage�Ƃ�����@�ł́A�e�^�X�N�ɂ��āA(�ŏ��̊�������)�ƁA(��Ԗڂɏ�������������)�̍����v�Z�����B���̒l�́Asufferage�ƌĂ΂�A�u���̃^�X�N���ŗǂ̃m�[�h�Ɋ��蓖�Ă��Ȃ��������ɁA���̃^�X�N�̏������ǂꂾ�������Ȃ��Ă��܂����v�������Ă���B�Ⴆ�Α傫�ȃf�[�^��p����^�X�N�ɂ����āA�f�[�^�����݂���m�[�h�ŏ�������ꍇ�ƁA���݂��Ȃ��m�[�h�ŏ�������ꍇ�ł́A�������������ɑ傫�ȍ����o��B���̂悤�ȃ^�X�N�ł�sufferage���傫���Ȃ�B���ɁA�S�Ẵ^�X�N�̒���sufferage���ł��傫���m�[�h���I�������B

������̎�@�ɂ����Ă��A�X�P�W���[������^�X�N��I��������A���̃^�X�N���ł�������������������m�[�h�Ɋ��蓖�Ă�B���̌�AETC�̍s��͍X�V�����B��̓I�ɂ́A���̃^�X�N���X�P�W���[�����O�\�ȃ��X�g����폜���A���蓖�Ă��m�[�h�����p�\�ɂȂ�܂ł̎��Ԃ��X�V����B�X�V���I�������A�V�����^�X�N�̊��蓖�ĂɈڂ�B

�����Greedy�Ȏ�@�̓����́A�������ȒP�ŏ������y���A���l�b�g���[�N��m�[�h�̍��G�x�̕ω��ɑ΂��ē��I�ɑΉ��ł���_�ł���B���_�Ƃ��ĂẮA�X�P�W���[�������ߒ��ɂ����āA��x�X�P�W���[�������^�X�N�̊��蓖�Ă͓�x�ƕύX����Ȃ����߁A�Ǐ��I�œK���Ɋׂ�₷���_����������B�܂��A���[�N�t���[�ɂ����ẮA��������̎q�^�X�N�����m�[�h�����s����Ȃ����Ƃɂ��A�S�̂�makespan�����тĂ��܂��\��������B�������A�ˑ����������Ȃ��W���u�̏W���ɑ΂��ẮAGA�Ȃǂ̂ɔ�ׂđ��F�Ȃ��Ƃ̌��ʂ��񍐂���Ă���B����ɂ��Ă͌���G���B



\subsection{GA}

�ÓI�ȃX�P�W���[�����O���ɑ΂��ẮAGA��Ă��݂��@(simulated annealing)���L�͂Ȏ�@�Ƃ��ċ�������B�����́A�̂Ƃ��Ĉ�̊��S�ȃX�P�W���[����p���A��������D�ꂽ�X�P�W���[���ɍX�V���Ă����B��莞�Ԏ��s��A������x�ǂ��X�P�W���[��������ꂽ�Ƃ���ōX�V���I�����A���̃X�P�W���[�����̗p����B�����ł�GA�ɂ��X�P�W���[�����O�A���S���Y���̎����ɂ��Đ�������B

�����̃A���S���Y����p����̂ɕK�v�ɂȂ�̂́A��`�q�̕\�����@�E�]���֐��E���G���@�ł���B��`�q�̕\�����@�Ƃ��ẮA�e�^�X�N���ǂ̃}�V���Ɋ��蓖�Ă����A���������z���p����̂��ł��P���ł���B����́A�ˑ����������A�t�s���l���Ȃ����f���̏ꍇ�A����m�[�h�Ɋ��蓖�Ă�ꂽ�^�X�N�̎��s�����́A�S�̂�makespan�ɉe�����Ȃ����߂ł���B�]���֐��Ƃ��ẮA����̏�������makespan��p����B���G���@�́A��̃X�P�W���[����r���ŕ������ĂȂ����킹����A�C�ӂ̗v�f�����ւ�����Ƃ�������@���l������B

�X�P�W���[�����O���ւ�GA�̗��p�͍L���s���Ă��āA�Ǐ��I�œK���Ɋׂ�ɂ����A�D�ꂽ�T�����\�������Ă���B����ŁA�������̂��d���A�T����Ԃ̑傫���ɔ�Ⴕ�����[�v�񐔂��K�v�ɂȂ邽�߁A�^�X�N���ƃm�[�h�����傫���Ȃ����ꍇ�A�v�Z�R�X�g�������ł��Ȃ��Ȃ�\��������B����ɑ΂��ẮA�^�X�N�W���S�̂�\�߂������̏����ȃ^�X�N�W���ɕ������A���ꂼ��ɂ��ĕʁX�ɃX�P�W���[�����O���s�����Ƃ��ł���B�܂���ɏq�ׂ���`�q�\���ɂ̓^�X�N�̎��s�������܂܂�Ă��Ȃ����߁Amakespan�����߂���X�P�W���[���Ƃ��Ď��s���邱�Ƃ��ł��Ȃ��B�܂��A�\�����@�ɂ���Ă͌��G�̍ۂɎ��s�s�\�ȃX�P�W���[������������Ă��܂��\��������B���̂��߁A��`�q�\�����H�v����K�v������B



\subsection{�e��@�̔�r}

Tracy�� \cite{eleven}�́A11��ނ̃X�P�W���[�����O��@���V�~�����[�V������p���Ĕ�r�����B�^�X�N�̃f�[�^�͗l�X�ȏ������Č�����悤�����_���ɐ�������A�e��@��p����makespan���r�����B

��r���ꂽ��@�̓����_���EMax-min�EMin-min�EGA�E�Ă��݂��@�EGSA�EA*�ȂǂŁA8�m�[�h�E512�^�X�N�̖��ɂ��āAPentiumII 300MHz�A������1GB�̊����ōs��ꂽ�B�f�[�^�́A�܂��e�^�X�N�ɂ��āA�������Ԃ̊�ƂȂ�l����l�����Ő������A����ɂ���Ɉ�l�������|�����킹�Đ�������Ă���B���ʂ́A��̏����ɑ΂�100�̈قȂ����s�񂪐�������A�e��@�ɂ��Ă̔�r���s��ꂽ�B���ʂ̈���}\ref{fig:eleven} �Ɏ����B

\begin{figure}[bthp]
	\begin{center}
	\includegraphics[scale=0.2]{11.eps}
	\end{center}
	\caption{Comparing scheduling heuristics (Partially-consistent, high task, high machine heterogeneity data)}
	\label{fig:eleven}
\end{figure}


�S�̂Ƃ��āA�قƂ�ǂ̏����ɂ�����GA�ɂ���ē���ꂽ�X�P�W���[�����ŒZ��makespan��^�������A�œK�l�𓾂�̂ɖ�ꕪ��v�����B
����ŁAMin-min�@�ɂ���ē���ꂽ�X�P�W���[����GA�œ���ꂽ���̂ɗ����̂́A�ł��ǂ��X�P�W���[������T��10\%���������Ȃ������B
���̂��Ƃ���A�^�X�N�ԂɈˑ����������A�t�s���l�����Ȃ��󋵂ɂ����ẮAMin-min�@�����p�I�ł���Ƃ������ʂ�����ꂽ�B



\section{Workflow�̃X�P�W���[�����O}

GrADS�v���W�F�N�g \cite{grads} �ł́A�f�[�^�E�C���e���V�u�Ȋ��ɑΉ������X�P�W�����[�̊J�����s���Ă���B

�����n�Ƃ��Č����X�P�W�����[�����������ŕK�{�ɂȂ�̂��A�A�v���P�[�V�����̎��s���Ԃ�t�@�C���T�C�Y��\�����邱�Ƃł���BGrADS�ł́A�܂��e�m�[�h�̐��\���A�������Z���\�E���������_���Z���\�ECPU�N���b�N�E�L���b�V���T�C�Y�E�������N���b�N�E�������T�C�Y�Ȃǂ�p���ăp�����[�^�����A�܂����ۂ̃v���O�����������ȃf�[�^�Ŏ��s���邱�ƂŃA�N�Z�X�p�^�[���𑪒肵�A�^�X�N�̎��s���Ԃ𐄑�����B�܂��t�@�C���]���̎��Ԃɂ��Ă��A�e�m�[�h�Ԃ̃o���h���E���C�e���V�𑪒肷�邱�Ƃŗ\������B�������āA���X�P�W���[���ȃ^�X�N�ɑ΂���ETC�s����v�Z���邱�Ƃ��ł���B

�X�P�W���[�����O�A���S���Y���Ƃ��ẮAGreedy�Ȏ�@��p���Ă���B�܂����[�N�t���[��Ŏ��s�\�ȃ^�X�N�̂�����ɑ΂��X�P�W���[�����O���s���A���̃^�X�N�����s�������Ƃɂ���Ď��s�\�ɂȂ����^�X�N�����s�\���X�g�ɉ�����B���̌�ETC�\���X�V���A���ԂɑS�Ẵ^�X�N���X�P�W���[�����O����܂ŌJ��Ԃ��B
�������S�ɓ��I�ɍs���̂ł͂Ȃ��AMax-min�EMin-min�Esufferage�̎O��@�ɂ��đS�^�X�N�����蓖�āA���S�ȃX�P�W���[�����쐬�����̂��A���̒��ōł�Makespan�����������̂�I������B

�����̍H�v�ɂ��AGrADS�X�P�W�����[�ł́A�����̃X�P�W�����[�ɔ�ׂČ����I�ȃX�P�W���[�����O�����������B��������؂��邽�߁A�摜�����̃^�X�N��p���Ĕ�r�������s��ꂽ�B�����ɂ͉摜�����̃f�[�^���p�����A�f�[�^�T�C�Y��2GB�ł������B������f���A��Itanium�EOpteron�v���Z�b�T�Ȃǂ����݂���271�v���Z�b�T�̊��Ŏ��s�����B�Ȃ�GrADS�̓��v���J�̔z�u�͎����ōs���Ȃ��̂ŁA�K�v�ɂȂ�f�[�^�͗\�ߊe�N���X�^�ɃR�s�[����A�f�[�^�]���̓N���X�^�Ԃł̂ݍs��ꂽ�B���̈�A�̃^�X�N�ɂ��āA�ȉ��̎l�̃X�P�W���[�����O���@�Ŏ������s���A���\����r���ꂽ�B

\begin{itemize}
\item RN : �����_���ȃX�P�W���[�����O
\item RA : ���S�Ȑ��\�\���ɑ΂��A�f�[�^�]���R�X�g���l�������A���\�ɉ��������̃^�X�N������t��������
\item HC : CPU�N���b�N�݂̂ɂ��ȒP�Ȑ��\�\���̂̂��AGreedy�ȃX�P�W���[���𗧂Ă�����
\item HA : ���S�Ȑ��\�\���̂̂��AGreedy�ȃX�P�W���[���𗧂Ă�����
\end{itemize}

���̌��ʂ�}\ref{fig:grads}�Ɏ����B


\begin{figure}[bthp]
\begin{center}
\begin{tabular}{|l||l|l|l|l|} 
\hline 
&HA & HC & RN & RA \\
\hline 
makespans (min) & 505 & 757 & 1121 & 762 \\
\hline 
\end{tabular} 
\end{center}
\caption{Makespans with GrADS and random scheduler}
\label{fig:grads}
\end{figure}

���̂悤�ɁA�����_���ȃX�P�W���[�����O���s�����ꍇ(RN)�ɔ�ׂĖ�2�{�̐��\���オ����ꂽ�B
�X�P�W���[���𕪐͂����Ƃ���A���\�\���ɂ���āA���\�̍����m�[�h�ɑ����̃^�X�N������U���Ă���l�q���ώ@�ł��A�e�}�V���̃��[�h�̕��ω��ɂ��v�������B


\section{�f�[�^�E�C���e���V�u���ɑΉ������X�P�W�����[}
Huadong�� \cite{huadong}�́A�f�[�^�E�C���e���V�u�Ȋ��ɑΉ������X�P�W���[�����O�A���S���Y���Ƃ��āA�t�@�C�����v���J�̔z�u���^�X�N�X�P�W���[�����O�Ɠ����Ɉ������@��񏥂��Ă���B%�Ȃ��A���̌����̖ړI��makespan���ŏ������邱�Ƃł͂Ȃ��A�Ɨ������e�^�X�N�̕��Ϗ������Ԃ�Z�k���邱�Ƃɐݒ肳��Ă���B
��{�I�ȃA�C�f�B�A�́A���\�̍����m�[�h�������I�ɔ������A���\�̍����m�[�h�ŗD��I�ɏ������s�����Ƃł���B�X�P�W���[�����O��1�^�X�N���s���邪�A�����̃^�X�N���X�P�W���[������ƁA���̃^�X�N�Q�̑S�Ẵ^�X�N����������܂ŐV�����^�X�N�̓X�P�W���[�����O����Ȃ��B

���̌����ł́A�ߋ��̃^�X�N�̎��s���Ԃ���m�[�h�̐��\��\�z����B����͐��\�\�����f���Ɋ�Â����̂ł͂Ȃ��A�e�^�X�N�̏d�����قڋψ�ł���Ƃ̉���Ɋ�Â��āA��^�X�N�̏������Ԃ��Z����ΐ��\�������ƍl����B���̂悤�ɂ��ė\�����ꂽ�e�m�[�h�̐��\�����ɁA���\�̍����Ɣ��f���ꂽ�m�[�h�ɗD��I�Ƀ^�X�N�̊��蓖�Ă��s���B�܂��A��x���蓖�Ă������ʂ��Ԃ��Ă��Ȃ��^�X�N�ɂ��ẮA��荂���ȃm�[�h���V�x��ԂɂȂ�ƁA���̃m�[�h�ł��������J�n����B���̃^�X�N�Ɋւ��ẮA�����ꂩ�̃m�[�h�����ʂ�Ԃ��ƁA��d�ɏ������Ă���m�[�h�͏����𒆎~����B

�f�[�^�E�C���e���V�u�Ȋ��ւ̑Ή��Ƃ��ẮA�X�P�W���[���\�ȃm�[�h����������ꍇ�A�f�[�^�]�����Ԃ��l�������X�P�W���[�����O���s���B���̍ۂ̃f�[�^�]�����Ԃ́A���ۂɃf�[�^�̈ꕔ��]�����A�v�������Ԃ��琄�肷��B�������邱�ƂŁA�ÓI�ȃo���h�������łȂ��A���s���̃l�b�g���[�N�̍��G�x�ɂ��������\�����s����B

���̃V�X�e���ɂ��āA���\���l�����Ȃ����@�E���\����݂̂��s���A�f�[�^�]�����Ԃ��l�����Ȃ����@�E�{��@�̎O�̕��@�ɂ��āA���ۂ̃A�v���P�[�V�����Ŕ�r���s��ꂽ�B������Planet Lab���80��̃m�[�h�ōs���A�S�̂̃f�[�^�T�C�Y��6.7GB�ł������B�Ȃ��A�m�[�h�͐�L����Ă��炸�A��ɑ��̃��[�U�[�̃A�v���P�[�V���������삵�Ă����B�����ɂ��āA��x�ɃX�P�W���[������^�X�N�̐���200, 400, 600, 800�ƕς��Ď������s��ꂽ�B���̒l���������ꍇ�ɂ͍Ċ��蓖�Ă��p�ɂɋN����A�^�X�N�̏������Ԃ͒Z���Ȃ�B���ʂ�}\ref{fig:huadong}�Ɏ����B


\begin{figure}[bthp]
	\begin{center}
	\includegraphics[scale=0.2]{huadong.eps}
	\end{center}
	\caption{}
	\label{fig:huadong}
\end{figure}


���̂悤�ɁA������̏����ɂ����Ă��{��@����20\%�Z��makespan��^�����B���̌����ł́A�X�P�W���[�����O�͋Ǐ��I�ɍs���Ă��邽�߁A���I�ɗǂ��X�P�W���[�����O���s����ۏ؂͖�������A���ۂɏ����n�Ƃ��Ď�������A���I�Ɋe�m�[�h�̕��ׂ�l�b�g���[�N�̍��G�x���ӂ܂����X�P�W���[�����O���s����_�ŕ]���ł���Ǝv����B


\section{�f�[�^�E�C���e���V�u���ɑΉ�����Workflow�̃X�P�W���[�����O}
�f�[�^�E�C���e���V�u�Ȋ����ł́A�����I�ȃ^�X�N�X�P�W���[�����O�ƂƂ��ɁA���ʓI�ȃt�@�C�����v���J�̔z�u���s���ƂȂ�BPhan�� \cite{phan}�́A�f�[�^�E�C���e���V�u�Ȋ��ɑΉ����āA�^�X�N�̃X�P�W���[�����O�ƃ��v���J�̔z�u�𓯎��Ɍv�悷��X�P�W���[�����O�A���S���Y�����Ă��Ă���B�܂��^�X�N�W���Ƃ��ă��[�N�t���[�������Ă���A

�����GA��p���Ă���A��`�q�\���Ƃ��ăX�P�W���[���ƃ��v���J�̔z�u�̗�����p���邱�ƂŁA�����I�ȃX�P�W���[�����O���\�ɂ��Ă���B


��`�q�͎O�̔z��ɂ���č\������Ă���B�܂���́A�S�^�X�N����񉻂������̂ł���B����́A���[�N�t���[�̎��s��������𖞂����悤�ɂȂ��Ă���B���ɁA�e�^�X�N�ɑ΂��Ċ��蓖�Ă���m�[�h�������ꂽ�z�񂪂���B����́A��̈ˑ��֌W���l���Ȃ��X�P�W�����[�ɂ����ėp����ꂽ�̂Ɠ���ł���B�Ō�ɁA�e���v���J�̔z�u�������z�񂪂���B���̎O���w�肷�邱�ƂŁA��̃X�P�W���[����\���悤�ɂȂ��Ă���B�]���֐��Ƃ��Ă�makespan��p���A���G�̓��[�N�t���[�̐���𖞂����^�X�N���������ւ�����A���v���J�̈ʒu���������邱�Ƃōs����B

���̃X�P�W���[�����O�A���S���Y���ƁA���Min-min�@�Ƀ����_���Ƀ��v���J��z�u�����@����r���ꂽ�B
GA�ł́A��������܂ł͒������s����قǗǂ�����������B�������A�X�P�W�����[�Ƃ��Ă̗v������A���100����̃V�~�����[�V�����őł��؂�ݒ�Ƃ���Ă���B
�^�X�N����40, 80, 160�ƕς��āA�������s��ꂽ�B

\begin{figure}[bthp]
	\begin{center}
	\includegraphics[scale=1.5]{phan.eps}
	\end{center}
	\caption{Makespans of GA (with automatically placed replicas) and Min-min (with randomly located replicas)}
	\label{fig:phan}
\end{figure}

���ʂ́A40�^�X�N�̏ꍇ�́A�{��@����{�قǗǂ����ʂƂȂ������A160�^�X�N�̏ꍇ�͂��̍��͂قڂȂ��Ȃ��Ă���B����́A�T����Ԃɔ�ׂ�GA�̐��㐔�����Ȃ����߁A�Ɛ�������Ă���B



\section{������}�
�{���\�ł́A�O���b�h���Ƀ^�X�N�𕪔z���镪�U�^�X�N�X�P�W���[���ɂ��Ă̒�����񍐂����B
�܂��A��ʓI�ȃ^�X�N�X�P�W�����[�̍l�����ׂ������ɂ��Đ���������A���[�N�t���[�ƃf�[�^�E�C���e���V�u�Ƃ����A�ߔN���ڂ���Ă����̊����N�����B
���ɁA�����̃^�X�N���z�A���S���Y���Ƃ��āAGreedy��Max-min�EMin-min�ESufferage�̎O��������A�����̎�@�̃V�~�����[�V�����ɂ�鐫�\��r���������B
����Greedy�ȃA���S���Y����p���āA���[�N�t���[�X�P�W�����[������������Ƃ��āAGrADS�v���W�F�N�g�̊T�v�Ɛ��ʂ�������A�Ō�Ƀf�[�^�C���e���V�u�Ȋ��ɓK�������A���[�N�t���[�X�P�W�����[�̌����Ƃ��āAGA��p����Phan��̌������Љ���B

����́A�����������Q�l�ɂ��A���ۂ̃l�b�g���[�N�g�|���W���l�������A�����I�ȃ��[�N�t���[�X�P�W�����[�̎�����i�߂Ă��������B
�܂��A�f�[�^�C���e���V�u�ȃA�v���P�[�V�����ɂ����ẮA���ԃt�@�C���̊Ǘ����d�v�Ȗ��ɂȂ�Ǝv����B���[�J���f�B�X�N���������m�[�h�ɂ����ẮA�m�[�h�ɕێ��ł���f�[�^�ʂɐ��񂪂���B���̂��߁A���ɕK�v�Ƃ���Ȃ��Ȃ����t�@�C����K�X�폜������A�K�v�ɉ����čĐ�������Ȃǂ̍H�v�����荞�݂����B



%\bibliographystyle{jplain}
%\bibliography{chuukan}
\biblio
\begin{thebibliography}{9}

\bibitem{taxonomy}
Jia Yu and Rajkumar Buyya
``A Taxonomy of Scientific Workflow Systems for Grid computing''
Special Issue on Scientific Workflows, SIGMOD Record, ACM Press, Volume 34, Number 3, Sept. 2005


\bibitem{condor}
J. Frey, T. Tannenbaum, I. Foster, M. Livny, and S. Tuecke, 
``Condor-G: A Computation Management Agent for Multi-Institutional Grids.,''
 Cluster Computing, vol. 5, pp. 237-246, 2002.

\bibitem{dagman}
http://www.cs.wisc.edu/condor/dagman/

\bibitem{pegasus}
Ewa Deelman1 et al.
``Pegasus: Mapping Scientific Workflows onto the Grid''
Lecture notes in computer science  (Lect. notes comput. sci.) Grid computing  (Nicosia, 28-30 January 2004, revised papers) 

\bibitem{pegasus2}
Luiz Meyer
``Planning spatial workflows to optimize grid performance''
Proceedings of the 2006 ACM symposium on Applied computing Dijon, France (DSGC) 


\bibitem{eleven}
Tracy et al. ``A Comparison Study of Eleven Static Heuristics for Mapping a Class of Independent Tasks onto Heterogeneous Distributed Computing Systems ''
(TR-ECE 00-04) 

\bibitem{titech}
���c�I�� ���V�^��N ���c�G�� ������
``���v���J�Ǘ��V�X�e���𗘗p�����f�[�^�C���e���V�u�A�v���P�[�V���������X�P�W���[�����O�V�X�e��''
�n�C�p�t�H�[�}���X�R���s���[�e�B���O�ƌv�Z�Ȋw�V���|�W�E��(HPCS2006), 2006, 9-16. 4, 

\bibitem{grads}
Mandal, A. et al.
``Scheduling Strategies for Mapping Application Workflows onto the Grid. ''
IEEE Symposium HPDC 14, 125.134. (2005)

\bibitem{grads2}
K. Cooper et al.
``New Grid Scheduling and Rescheduling Methods in the GrADS Project''
Parallel and Distributed Processing Symposium, 2004. Proceedings. 18th International (2004)


\bibitem{huadong}
Huadong et al. ``Dynamic Co-Scheduling of Distributed Computation and Replication''
Proceedings of the Sixth IEEE International Symposium on Cluster Computing and the Grid (CCGRID'06) - Volume 00 CCGRID '06 

\bibitem{phan}
Phan et al. ``Evolving toward the perfect schedule: Co-scheduling job
assignments and data replication in wide-area systems using a genetic algorithm.''
 In Proceedings of the11th Workshop on Job Scheduling Strategies for Parallel 
Processing. Cambridge, MA. Springer-Verlag, Berlin, Germany 2005

\bibitem{triana}
A. Tsalgatidou, G. Athanasopoulos, M. Pantazoglou, C. Pautasso, T. Heinis, R. Gronmo, Hjordis Hoff, Arne-Jorgen Berre, M. Glittum, S. Topouzidou  
``Developing scientific workflows from heterogeneous services ''
June 2006    ACM SIGMOD Record,  Volume 35 Issue 2  
 

\bibitem{sawzall}
Rob Pike, Sean Dorward, Robert Griesemer, Sean Quinlan
``Interpreting the Data: Parallel Analysis with Sawzall''
http://abs.google.com/papers/sawzall-sciprog.pdf




\end{thebibliography}

\end{document}